LCOV - code coverage report
Current view: top level - source/third_party/mikktspace - mikktspace.cpp (source / functions) Hit Total Coverage
Test: 0 A.D. test coverage report Lines: 0 939 0.0 %
Date: 2022-06-14 00:41:00 Functions: 0 24 0.0 %

          Line data    Source code
       1             : // Slightly modified version of mikktspace, by Wildfire Games, for 0 A.D.
       2             : // 
       3             : // Motivation for changes:
       4             : //  * For quietness with our default warning flags, some warnings are
       5             : //    explicitly disabled.
       6             : 
       7             : #include "precompiled.h"
       8             : 
       9             : #ifdef _MSC_VER
      10             : # pragma warning(disable:4456) // hides previous local declaration
      11             : # pragma warning(disable:4189) // local variable is initialized but not referenced
      12             : #endif
      13             : 
      14             : #ifdef __GNUC__
      15             : # pragma GCC diagnostic ignored "-Wunused-variable"
      16             : #endif
      17             : 
      18             : /** \file mikktspace/mikktspace.c
      19             :  *  \ingroup mikktspace
      20             :  */
      21             : /**
      22             :  *  Copyright (C) 2011 by Morten S. Mikkelsen
      23             :  *
      24             :  *  This software is provided 'as-is', without any express or implied
      25             :  *  warranty.  In no event will the authors be held liable for any damages
      26             :  *  arising from the use of this software.
      27             :  *
      28             :  *  Permission is granted to anyone to use this software for any purpose,
      29             :  *  including commercial applications, and to alter it and redistribute it
      30             :  *  freely, subject to the following restrictions:
      31             :  *
      32             :  *  1. The origin of this software must not be misrepresented; you must not
      33             :  *     claim that you wrote the original software. If you use this software
      34             :  *     in a product, an acknowledgment in the product documentation would be
      35             :  *     appreciated but is not required.
      36             :  *  2. Altered source versions must be plainly marked as such, and must not be
      37             :  *     misrepresented as being the original software.
      38             :  *  3. This notice may not be removed or altered from any source distribution.
      39             :  */
      40             : 
      41             : #include <assert.h>
      42             : #include <stdio.h>
      43             : #include <math.h>
      44             : #include <string.h>
      45             : #include <float.h>
      46             : #include <stdlib.h>
      47             : 
      48             : #include "mikktspace.h"
      49             : 
      50             : #define TFALSE      0
      51             : #define TTRUE       1
      52             : 
      53             : #ifndef M_PI
      54             : #define M_PI    3.1415926535897932384626433832795
      55             : #endif
      56             : 
      57             : #define INTERNAL_RND_SORT_SEED      39871946
      58             : 
      59             : // internal structure
      60             : typedef struct
      61             : {
      62             :     float x, y, z;
      63             : } SVec3;
      64             : 
      65             : static tbool            veq( const SVec3 v1, const SVec3 v2 )
      66             : {
      67           0 :     return (v1.x == v2.x) && (v1.y == v2.y) && (v1.z == v2.z);
      68             : }
      69             : 
      70             : static SVec3        vadd( const SVec3 v1, const SVec3 v2 )
      71             : {
      72           0 :     SVec3 vRes;
      73             : 
      74           0 :     vRes.x = v1.x + v2.x;
      75           0 :     vRes.y = v1.y + v2.y;
      76           0 :     vRes.z = v1.z + v2.z;
      77             : 
      78           0 :     return vRes;
      79             : }
      80             : 
      81             : 
      82             : static SVec3        vsub( const SVec3 v1, const SVec3 v2 )
      83             : {
      84           0 :     SVec3 vRes;
      85             : 
      86           0 :     vRes.x = v1.x - v2.x;
      87           0 :     vRes.y = v1.y - v2.y;
      88           0 :     vRes.z = v1.z - v2.z;
      89             : 
      90           0 :     return vRes;
      91             : }
      92             : 
      93             : static SVec3        vscale(const float fS, const SVec3 v)
      94             : {
      95           0 :     SVec3 vRes;
      96             : 
      97           0 :     vRes.x = fS * v.x;
      98           0 :     vRes.y = fS * v.y;
      99           0 :     vRes.z = fS * v.z;
     100             : 
     101           0 :     return vRes;
     102             : }
     103             : 
     104             : static float            LengthSquared( const SVec3 v )
     105             : {
     106           0 :     return v.x*v.x + v.y*v.y + v.z*v.z;
     107             : }
     108             : 
     109             : static float            Length( const SVec3 v )
     110             : {
     111           0 :     return sqrtf(LengthSquared(v));
     112             : }
     113             : 
     114           0 : static SVec3        Normalize( const SVec3 v )
     115             : {
     116           0 :     return vscale(1 / Length(v), v);
     117             : }
     118             : 
     119             : static float        vdot( const SVec3 v1, const SVec3 v2)
     120             : {
     121           0 :     return v1.x*v2.x + v1.y*v2.y + v1.z*v2.z;
     122             : }
     123             : 
     124             : 
     125             : static tbool NotZero(const float fX)
     126             : {
     127             :     // could possibly use FLT_EPSILON instead
     128           0 :     return fabsf(fX) > FLT_MIN;
     129             : }
     130             : 
     131             : static tbool VNotZero(const SVec3 v)
     132             : {
     133             :     // might change this to an epsilon based test
     134           0 :     return NotZero(v.x) || NotZero(v.y) || NotZero(v.z);
     135             : }
     136             : 
     137             : 
     138             : 
     139             : typedef struct
     140             : {
     141             :     int iNrFaces;
     142             :     int * pTriMembers;
     143             : } SSubGroup;
     144             : 
     145             : typedef struct
     146             : {
     147             :     int iNrFaces;
     148             :     int * pFaceIndices;
     149             :     int iVertexRepresentitive;
     150             :     tbool bOrientPreservering;
     151             : } SGroup;
     152             : 
     153             : // 
     154             : #define MARK_DEGENERATE             1
     155             : #define QUAD_ONE_DEGEN_TRI          2
     156             : #define GROUP_WITH_ANY              4
     157             : #define ORIENT_PRESERVING           8
     158             : 
     159             : 
     160             : 
     161             : typedef struct
     162             : {
     163             :     int FaceNeighbors[3];
     164             :     SGroup * AssignedGroup[3];
     165             :     
     166             :     // normalized first order face derivatives
     167             :     SVec3 vOs, vOt;
     168             :     float fMagS, fMagT; // original magnitudes
     169             : 
     170             :     // determines if the current and the next triangle are a quad.
     171             :     int iOrgFaceNumber;
     172             :     int iFlag, iTSpacesOffs;
     173             :     unsigned char vert_num[4];
     174             : } STriInfo;
     175             : 
     176             : typedef struct
     177             : {
     178             :     SVec3 vOs;
     179             :     float fMagS;
     180             :     SVec3 vOt;
     181             :     float fMagT;
     182             :     int iCounter;   // this is to average back into quads.
     183             :     tbool bOrient;
     184             : } STSpace;
     185             : 
     186             : static int GenerateInitialVerticesIndexList(STriInfo pTriInfos[], int piTriList_out[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn);
     187             : static void GenerateSharedVerticesIndexList(int piTriList_in_and_out[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn);
     188             : static void InitTriInfo(STriInfo pTriInfos[], const int piTriListIn[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn);
     189             : static int Build4RuleGroups(STriInfo pTriInfos[], SGroup pGroups[], int piGroupTrianglesBuffer[], const int piTriListIn[], const int iNrTrianglesIn);
     190             : static tbool GenerateTSpaces(STSpace psTspace[], const STriInfo pTriInfos[], const SGroup pGroups[],
     191             :                              const int iNrActiveGroups, const int piTriListIn[], const float fThresCos,
     192             :                              const SMikkTSpaceContext * pContext);
     193             : 
     194             : static int MakeIndex(const int iFace, const int iVert)
     195             : {
     196           0 :     assert(iVert>=0 && iVert<4 && iFace>=0);
     197           0 :     return (iFace<<2) | (iVert&0x3);
     198             : }
     199             : 
     200             : static void IndexToData(int * piFace, int * piVert, const int iIndexIn)
     201             : {
     202           0 :     piVert[0] = iIndexIn&0x3;
     203           0 :     piFace[0] = iIndexIn>>2;
     204             : }
     205             : 
     206           0 : static STSpace AvgTSpace(const STSpace * pTS0, const STSpace * pTS1)
     207             : {
     208           0 :     STSpace ts_res;
     209             : 
     210             :     // this if is important. Due to floating point precision
     211             :     // averaging when ts0==ts1 will cause a slight difference
     212             :     // which results in tangent space splits later on
     213           0 :     if (pTS0->fMagS==pTS1->fMagS && pTS0->fMagT==pTS1->fMagT &&
     214           0 :        veq(pTS0->vOs,pTS1->vOs)   && veq(pTS0->vOt, pTS1->vOt))
     215             :     {
     216           0 :         ts_res.fMagS = pTS0->fMagS;
     217           0 :         ts_res.fMagT = pTS0->fMagT;
     218           0 :         ts_res.vOs = pTS0->vOs;
     219           0 :         ts_res.vOt = pTS0->vOt;
     220             :     }
     221             :     else
     222             :     {
     223           0 :         ts_res.fMagS = 0.5f*(pTS0->fMagS+pTS1->fMagS);
     224           0 :         ts_res.fMagT = 0.5f*(pTS0->fMagT+pTS1->fMagT);
     225           0 :         ts_res.vOs = vadd(pTS0->vOs,pTS1->vOs);
     226           0 :         ts_res.vOt = vadd(pTS0->vOt,pTS1->vOt);
     227           0 :         if ( VNotZero(ts_res.vOs) ) ts_res.vOs = Normalize(ts_res.vOs);
     228           0 :         if ( VNotZero(ts_res.vOt) ) ts_res.vOt = Normalize(ts_res.vOt);
     229             :     }
     230             : 
     231           0 :     return ts_res;
     232             : }
     233             : 
     234             : 
     235             : 
     236             : static SVec3 GetPosition(const SMikkTSpaceContext * pContext, const int index);
     237             : static SVec3 GetNormal(const SMikkTSpaceContext * pContext, const int index);
     238             : static SVec3 GetTexCoord(const SMikkTSpaceContext * pContext, const int index);
     239             : 
     240             : 
     241             : // degen triangles
     242             : static void DegenPrologue(STriInfo pTriInfos[], int piTriList_out[], const int iNrTrianglesIn, const int iTotTris);
     243             : static void DegenEpilogue(STSpace psTspace[], STriInfo pTriInfos[], int piTriListIn[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn, const int iTotTris);
     244             : 
     245             : 
     246           0 : tbool genTangSpaceDefault(const SMikkTSpaceContext * pContext)
     247             : {
     248           0 :     return genTangSpace(pContext, 180.0f);
     249             : }
     250             : 
     251           0 : tbool genTangSpace(const SMikkTSpaceContext * pContext, const float fAngularThreshold)
     252             : {
     253             :     // count nr_triangles
     254           0 :     int * piTriListIn = NULL, * piGroupTrianglesBuffer = NULL;
     255           0 :     STriInfo * pTriInfos = NULL;
     256           0 :     SGroup * pGroups = NULL;
     257           0 :     STSpace * psTspace = NULL;
     258           0 :     int iNrTrianglesIn = 0, f=0, t=0, i=0;
     259           0 :     int iNrTSPaces = 0, iTotTris = 0, iDegenTriangles = 0, iNrMaxGroups = 0;
     260           0 :     int iNrActiveGroups = 0, index = 0;
     261           0 :     const int iNrFaces = pContext->m_pInterface->m_getNumFaces(pContext);
     262           0 :     tbool bRes = TFALSE;
     263           0 :     const float fThresCos = (float) cos((fAngularThreshold*(float)M_PI)/180.0f);
     264             : 
     265             :     // verify all call-backs have been set
     266           0 :     if ( pContext->m_pInterface->m_getNumFaces==NULL ||
     267           0 :         pContext->m_pInterface->m_getNumVerticesOfFace==NULL ||
     268           0 :         pContext->m_pInterface->m_getPosition==NULL ||
     269           0 :         pContext->m_pInterface->m_getNormal==NULL ||
     270           0 :         pContext->m_pInterface->m_getTexCoord==NULL )
     271             :         return TFALSE;
     272             : 
     273             :     // count triangles on supported faces
     274           0 :     for (f=0; f<iNrFaces; f++)
     275             :     {
     276           0 :         const int verts = pContext->m_pInterface->m_getNumVerticesOfFace(pContext, f);
     277           0 :         if (verts==3) ++iNrTrianglesIn;
     278           0 :         else if(verts==4) iNrTrianglesIn += 2;
     279             :     }
     280           0 :     if (iNrTrianglesIn<=0) return TFALSE;
     281             : 
     282             :     // allocate memory for an index list
     283           0 :     piTriListIn = (int *) malloc(sizeof(int)*3*iNrTrianglesIn);
     284           0 :     pTriInfos = (STriInfo *) malloc(sizeof(STriInfo)*iNrTrianglesIn);
     285           0 :     if (piTriListIn==NULL || pTriInfos==NULL)
     286             :     {
     287           0 :         if (piTriListIn!=NULL) free(piTriListIn);
     288           0 :         if (pTriInfos!=NULL) free(pTriInfos);
     289           0 :         return TFALSE;
     290             :     }
     291             : 
     292             :     // make an initial triangle --> face index list
     293           0 :     iNrTSPaces = GenerateInitialVerticesIndexList(pTriInfos, piTriListIn, pContext, iNrTrianglesIn);
     294             : 
     295             :     // make a welded index list of identical positions and attributes (pos, norm, texc)
     296             :     //printf("gen welded index list begin\n");
     297           0 :     GenerateSharedVerticesIndexList(piTriListIn, pContext, iNrTrianglesIn);
     298             :     //printf("gen welded index list end\n");
     299             : 
     300             :     // Mark all degenerate triangles
     301           0 :     iTotTris = iNrTrianglesIn;
     302           0 :     iDegenTriangles = 0;
     303           0 :     for (t=0; t<iTotTris; t++)
     304             :     {
     305           0 :         const int i0 = piTriListIn[t*3+0];
     306           0 :         const int i1 = piTriListIn[t*3+1];
     307           0 :         const int i2 = piTriListIn[t*3+2];
     308           0 :         const SVec3 p0 = GetPosition(pContext, i0);
     309           0 :         const SVec3 p1 = GetPosition(pContext, i1);
     310           0 :         const SVec3 p2 = GetPosition(pContext, i2);
     311           0 :         if (veq(p0,p1) || veq(p0,p2) || veq(p1,p2)) // degenerate
     312             :         {
     313           0 :             pTriInfos[t].iFlag |= MARK_DEGENERATE;
     314           0 :             ++iDegenTriangles;
     315             :         }
     316             :     }
     317           0 :     iNrTrianglesIn = iTotTris - iDegenTriangles;
     318             : 
     319             :     // mark all triangle pairs that belong to a quad with only one
     320             :     // good triangle. These need special treatment in DegenEpilogue().
     321             :     // Additionally, move all good triangles to the start of
     322             :     // pTriInfos[] and piTriListIn[] without changing order and
     323             :     // put the degenerate triangles last.
     324           0 :     DegenPrologue(pTriInfos, piTriListIn, iNrTrianglesIn, iTotTris);
     325             : 
     326             :     
     327             :     // evaluate triangle level attributes and neighbor list
     328             :     //printf("gen neighbors list begin\n");
     329           0 :     InitTriInfo(pTriInfos, piTriListIn, pContext, iNrTrianglesIn);
     330             :     //printf("gen neighbors list end\n");
     331             : 
     332             :     
     333             :     // based on the 4 rules, identify groups based on connectivity
     334           0 :     iNrMaxGroups = iNrTrianglesIn*3;
     335           0 :     pGroups = (SGroup *) malloc(sizeof(SGroup)*iNrMaxGroups);
     336           0 :     piGroupTrianglesBuffer = (int *) malloc(sizeof(int)*iNrTrianglesIn*3);
     337           0 :     if (pGroups==NULL || piGroupTrianglesBuffer==NULL)
     338             :     {
     339           0 :         if (pGroups!=NULL) free(pGroups);
     340           0 :         if (piGroupTrianglesBuffer!=NULL) free(piGroupTrianglesBuffer);
     341           0 :         free(piTriListIn);
     342           0 :         free(pTriInfos);
     343           0 :         return TFALSE;
     344             :     }
     345             :     //printf("gen 4rule groups begin\n");
     346           0 :     iNrActiveGroups =
     347           0 :         Build4RuleGroups(pTriInfos, pGroups, piGroupTrianglesBuffer, piTriListIn, iNrTrianglesIn);
     348             :     //printf("gen 4rule groups end\n");
     349             : 
     350             :     //
     351             : 
     352           0 :     psTspace = (STSpace *) malloc(sizeof(STSpace)*iNrTSPaces);
     353           0 :     if (psTspace==NULL)
     354             :     {
     355           0 :         free(piTriListIn);
     356           0 :         free(pTriInfos);
     357           0 :         free(pGroups);
     358           0 :         free(piGroupTrianglesBuffer);
     359           0 :         return TFALSE;
     360             :     }
     361           0 :     memset(psTspace, 0, sizeof(STSpace)*iNrTSPaces);
     362           0 :     for (t=0; t<iNrTSPaces; t++)
     363             :     {
     364           0 :         psTspace[t].vOs.x=1.0f; psTspace[t].vOs.y=0.0f; psTspace[t].vOs.z=0.0f; psTspace[t].fMagS = 1.0f;
     365           0 :         psTspace[t].vOt.x=0.0f; psTspace[t].vOt.y=1.0f; psTspace[t].vOt.z=0.0f; psTspace[t].fMagT = 1.0f;
     366             :     }
     367             : 
     368             :     // make tspaces, each group is split up into subgroups if necessary
     369             :     // based on fAngularThreshold. Finally a tangent space is made for
     370             :     // every resulting subgroup
     371             :     //printf("gen tspaces begin\n");
     372           0 :     bRes = GenerateTSpaces(psTspace, pTriInfos, pGroups, iNrActiveGroups, piTriListIn, fThresCos, pContext);
     373             :     //printf("gen tspaces end\n");
     374             :     
     375             :     // clean up
     376           0 :     free(pGroups);
     377           0 :     free(piGroupTrianglesBuffer);
     378             : 
     379           0 :     if (!bRes)  // if an allocation in GenerateTSpaces() failed
     380             :     {
     381             :         // clean up and return false
     382           0 :         free(pTriInfos); free(piTriListIn); free(psTspace);
     383           0 :         return TFALSE;
     384             :     }
     385             : 
     386             : 
     387             :     // degenerate quads with one good triangle will be fixed by copying a space from
     388             :     // the good triangle to the coinciding vertex.
     389             :     // all other degenerate triangles will just copy a space from any good triangle
     390             :     // with the same welded index in piTriListIn[].
     391           0 :     DegenEpilogue(psTspace, pTriInfos, piTriListIn, pContext, iNrTrianglesIn, iTotTris);
     392             : 
     393           0 :     free(pTriInfos); free(piTriListIn);
     394             : 
     395           0 :     index = 0;
     396           0 :     for (f=0; f<iNrFaces; f++)
     397             :     {
     398           0 :         const int verts = pContext->m_pInterface->m_getNumVerticesOfFace(pContext, f);
     399           0 :         if (verts!=3 && verts!=4) continue;
     400             :         
     401             : 
     402             :         // I've decided to let degenerate triangles and group-with-anythings
     403             :         // vary between left/right hand coordinate systems at the vertices.
     404             :         // All healthy triangles on the other hand are built to always be either or.
     405             : 
     406             :         /*// force the coordinate system orientation to be uniform for every face.
     407             :         // (this is already the case for good triangles but not for
     408             :         // degenerate ones and those with bGroupWithAnything==true)
     409             :         bool bOrient = psTspace[index].bOrient;
     410             :         if (psTspace[index].iCounter == 0)  // tspace was not derived from a group
     411             :         {
     412             :             // look for a space created in GenerateTSpaces() by iCounter>0
     413             :             bool bNotFound = true;
     414             :             int i=1;
     415             :             while (i<verts && bNotFound)
     416             :             {
     417             :                 if (psTspace[index+i].iCounter > 0) bNotFound=false;
     418             :                 else ++i;
     419             :             }
     420             :             if (!bNotFound) bOrient = psTspace[index+i].bOrient;
     421             :         }*/
     422             : 
     423             :         // set data
     424           0 :         for (i=0; i<verts; i++)
     425             :         {
     426           0 :             const STSpace * pTSpace = &psTspace[index];
     427           0 :             float tang[] = {pTSpace->vOs.x, pTSpace->vOs.y, pTSpace->vOs.z};
     428           0 :             float bitang[] = {pTSpace->vOt.x, pTSpace->vOt.y, pTSpace->vOt.z};
     429           0 :             if (pContext->m_pInterface->m_setTSpace!=NULL)
     430           0 :                 pContext->m_pInterface->m_setTSpace(pContext, tang, bitang, pTSpace->fMagS, pTSpace->fMagT, pTSpace->bOrient, f, i);
     431           0 :             if (pContext->m_pInterface->m_setTSpaceBasic!=NULL)
     432           0 :                 pContext->m_pInterface->m_setTSpaceBasic(pContext, tang, pTSpace->bOrient==TTRUE ? 1.0f : (-1.0f), f, i);
     433             : 
     434           0 :             ++index;
     435             :         }
     436             :     }
     437             : 
     438           0 :     free(psTspace);
     439             : 
     440             :     
     441           0 :     return TTRUE;
     442             : }
     443             : 
     444             : ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
     445             : 
     446             : typedef struct
     447             : {
     448             :     float vert[3];
     449             :     int index;
     450             : } STmpVert;
     451             : 
     452             : const int g_iCells = 2048;
     453             : 
     454             : #ifdef _MSC_VER
     455             :     #define NOINLINE __declspec(noinline)
     456             : #else
     457             :     #define NOINLINE __attribute__ ((noinline))
     458             : #endif
     459             : 
     460             : // it is IMPORTANT that this function is called to evaluate the hash since
     461             : // inlining could potentially reorder instructions and generate different
     462             : // results for the same effective input value fVal.
     463           0 : NOINLINE int FindGridCell(const float fMin, const float fMax, const float fVal)
     464             : {
     465           0 :     const float fIndex = g_iCells * ((fVal-fMin)/(fMax-fMin));
     466           0 :     const int iIndex = fIndex<0?0:((int)fIndex);
     467           0 :     return iIndex<g_iCells?iIndex:(g_iCells-1);
     468             : }
     469             : 
     470             : static void MergeVertsFast(int piTriList_in_and_out[], STmpVert pTmpVert[], const SMikkTSpaceContext * pContext, const int iL_in, const int iR_in);
     471             : static void MergeVertsSlow(int piTriList_in_and_out[], const SMikkTSpaceContext * pContext, const int pTable[], const int iEntries);
     472             : static void GenerateSharedVerticesIndexListSlow(int piTriList_in_and_out[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn);
     473             : 
     474           0 : static void GenerateSharedVerticesIndexList(int piTriList_in_and_out[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn)
     475             : {
     476             : 
     477             :     // Generate bounding box
     478           0 :     int * piHashTable=NULL, * piHashCount=NULL, * piHashOffsets=NULL, * piHashCount2=NULL;
     479           0 :     STmpVert * pTmpVert = NULL;
     480           0 :     int i=0, iChannel=0, k=0, e=0;
     481           0 :     int iMaxCount=0;
     482           0 :     SVec3 vMin = GetPosition(pContext, 0), vMax = vMin, vDim;
     483           0 :     float fMin, fMax;
     484           0 :     for (i=1; i<(iNrTrianglesIn*3); i++)
     485             :     {
     486           0 :         const int index = piTriList_in_and_out[i];
     487             : 
     488           0 :         const SVec3 vP = GetPosition(pContext, index);
     489           0 :         if (vMin.x > vP.x) vMin.x = vP.x;
     490           0 :         else if(vMax.x < vP.x) vMax.x = vP.x;
     491           0 :         if (vMin.y > vP.y) vMin.y = vP.y;
     492           0 :         else if(vMax.y < vP.y) vMax.y = vP.y;
     493           0 :         if (vMin.z > vP.z) vMin.z = vP.z;
     494           0 :         else if(vMax.z < vP.z) vMax.z = vP.z;
     495             :     }
     496             : 
     497           0 :     vDim = vsub(vMax,vMin);
     498           0 :     iChannel = 0;
     499           0 :     fMin = vMin.x; fMax=vMax.x;
     500           0 :     if (vDim.y>vDim.x && vDim.y>vDim.z)
     501             :     {
     502             :         iChannel=1;
     503             :         fMin = vMin.y, fMax=vMax.y;
     504             :     }
     505           0 :     else if(vDim.z>vDim.x)
     506             :     {
     507           0 :         iChannel=2;
     508           0 :         fMin = vMin.z, fMax=vMax.z;
     509             :     }
     510             : 
     511             :     // make allocations
     512           0 :     piHashTable = (int *) malloc(sizeof(int)*iNrTrianglesIn*3);
     513           0 :     piHashCount = (int *) malloc(sizeof(int)*g_iCells);
     514           0 :     piHashOffsets = (int *) malloc(sizeof(int)*g_iCells);
     515           0 :     piHashCount2 = (int *) malloc(sizeof(int)*g_iCells);
     516             : 
     517           0 :     if (piHashTable==NULL || piHashCount==NULL || piHashOffsets==NULL || piHashCount2==NULL)
     518             :     {
     519           0 :         if (piHashTable!=NULL) free(piHashTable);
     520           0 :         if (piHashCount!=NULL) free(piHashCount);
     521           0 :         if (piHashOffsets!=NULL) free(piHashOffsets);
     522           0 :         if (piHashCount2!=NULL) free(piHashCount2);
     523           0 :         GenerateSharedVerticesIndexListSlow(piTriList_in_and_out, pContext, iNrTrianglesIn);
     524           0 :         return;
     525             :     }
     526           0 :     memset(piHashCount, 0, sizeof(int)*g_iCells);
     527           0 :     memset(piHashCount2, 0, sizeof(int)*g_iCells);
     528             : 
     529             :     // count amount of elements in each cell unit
     530           0 :     for (i=0; i<(iNrTrianglesIn*3); i++)
     531             :     {
     532           0 :         const int index = piTriList_in_and_out[i];
     533           0 :         const SVec3 vP = GetPosition(pContext, index);
     534           0 :         const float fVal = iChannel==0 ? vP.x : (iChannel==1 ? vP.y : vP.z);
     535           0 :         const int iCell = FindGridCell(fMin, fMax, fVal);
     536           0 :         ++piHashCount[iCell];
     537             :     }
     538             : 
     539             :     // evaluate start index of each cell.
     540           0 :     piHashOffsets[0]=0;
     541           0 :     for (k=1; k<g_iCells; k++)
     542           0 :         piHashOffsets[k]=piHashOffsets[k-1]+piHashCount[k-1];
     543             : 
     544             :     // insert vertices
     545           0 :     for (i=0; i<(iNrTrianglesIn*3); i++)
     546             :     {
     547           0 :         const int index = piTriList_in_and_out[i];
     548           0 :         const SVec3 vP = GetPosition(pContext, index);
     549           0 :         const float fVal = iChannel==0 ? vP.x : (iChannel==1 ? vP.y : vP.z);
     550           0 :         const int iCell = FindGridCell(fMin, fMax, fVal);
     551           0 :         int * pTable = NULL;
     552             : 
     553           0 :         assert(piHashCount2[iCell]<piHashCount[iCell]);
     554           0 :         pTable = &piHashTable[piHashOffsets[iCell]];
     555           0 :         pTable[piHashCount2[iCell]] = i;    // vertex i has been inserted.
     556           0 :         ++piHashCount2[iCell];
     557             :     }
     558             :     for (k=0; k<g_iCells; k++)
     559             :         assert(piHashCount2[k] == piHashCount[k]);  // verify the count
     560           0 :     free(piHashCount2);
     561             : 
     562             :     // find maximum amount of entries in any hash entry
     563           0 :     iMaxCount = piHashCount[0];
     564           0 :     for (k=1; k<g_iCells; k++)
     565           0 :         if (iMaxCount<piHashCount[k])
     566           0 :             iMaxCount=piHashCount[k];
     567           0 :     pTmpVert = (STmpVert *) malloc(sizeof(STmpVert)*iMaxCount);
     568             :     
     569             : 
     570             :     // complete the merge
     571           0 :     for (k=0; k<g_iCells; k++)
     572             :     {
     573             :         // extract table of cell k and amount of entries in it
     574           0 :         int * pTable = &piHashTable[piHashOffsets[k]];
     575           0 :         const int iEntries = piHashCount[k];
     576           0 :         if (iEntries < 2) continue;
     577             : 
     578           0 :         if (pTmpVert!=NULL)
     579             :         {
     580           0 :             for (e=0; e<iEntries; e++)
     581             :             {
     582           0 :                 int i = pTable[e];
     583           0 :                 const SVec3 vP = GetPosition(pContext, piTriList_in_and_out[i]);
     584           0 :                 pTmpVert[e].vert[0] = vP.x; pTmpVert[e].vert[1] = vP.y;
     585           0 :                 pTmpVert[e].vert[2] = vP.z; pTmpVert[e].index = i;
     586             :             }
     587           0 :             MergeVertsFast(piTriList_in_and_out, pTmpVert, pContext, 0, iEntries-1);
     588             :         }
     589             :         else
     590           0 :             MergeVertsSlow(piTriList_in_and_out, pContext, pTable, iEntries);
     591             :     }
     592             : 
     593           0 :     if (pTmpVert!=NULL) { free(pTmpVert); }
     594           0 :     free(piHashTable);
     595           0 :     free(piHashCount);
     596           0 :     free(piHashOffsets);
     597             : }
     598             : 
     599           0 : static void MergeVertsFast(int piTriList_in_and_out[], STmpVert pTmpVert[], const SMikkTSpaceContext * pContext, const int iL_in, const int iR_in)
     600             : {
     601             :     // make bbox
     602           0 :     int c=0, l=0, channel=0;
     603           0 :     float fvMin[3], fvMax[3];
     604           0 :     float dx=0, dy=0, dz=0, fSep=0;
     605           0 :     for (c=0; c<3; c++)
     606           0 :     {   fvMin[c]=pTmpVert[iL_in].vert[c]; fvMax[c]=fvMin[c];    }
     607           0 :     for (l=(iL_in+1); l<=iR_in; l++)
     608           0 :         for (c=0; c<3; c++)
     609           0 :             if (fvMin[c]>pTmpVert[l].vert[c]) fvMin[c]=pTmpVert[l].vert[c];
     610           0 :             else if(fvMax[c]<pTmpVert[l].vert[c]) fvMax[c]=pTmpVert[l].vert[c];
     611             : 
     612           0 :     dx = fvMax[0]-fvMin[0];
     613           0 :     dy = fvMax[1]-fvMin[1];
     614           0 :     dz = fvMax[2]-fvMin[2];
     615             : 
     616           0 :     channel = 0;
     617           0 :     if (dy>dx && dy>dz) channel=1;
     618           0 :     else if(dz>dx) channel=2;
     619             : 
     620           0 :     fSep = 0.5f*(fvMax[channel]+fvMin[channel]);
     621             : 
     622             :     // terminate recursion when the separation/average value
     623             :     // is no longer strictly between fMin and fMax values.
     624           0 :     if (fSep>=fvMax[channel] || fSep<=fvMin[channel])
     625             :     {
     626             :         // complete the weld
     627           0 :         for (l=iL_in; l<=iR_in; l++)
     628             :         {
     629           0 :             int i = pTmpVert[l].index;
     630           0 :             const int index = piTriList_in_and_out[i];
     631           0 :             const SVec3 vP = GetPosition(pContext, index);
     632           0 :             const SVec3 vN = GetNormal(pContext, index);
     633           0 :             const SVec3 vT = GetTexCoord(pContext, index);
     634             : 
     635           0 :             tbool bNotFound = TTRUE;
     636           0 :             int l2=iL_in, i2rec=-1;
     637           0 :             while (l2<l && bNotFound)
     638             :             {
     639           0 :                 const int i2 = pTmpVert[l2].index;
     640           0 :                 const int index2 = piTriList_in_and_out[i2];
     641           0 :                 const SVec3 vP2 = GetPosition(pContext, index2);
     642           0 :                 const SVec3 vN2 = GetNormal(pContext, index2);
     643           0 :                 const SVec3 vT2 = GetTexCoord(pContext, index2);
     644           0 :                 i2rec=i2;
     645             : 
     646             :                 //if(vP==vP2 && vN==vN2 && vT==vT2)
     647           0 :                 if (vP.x==vP2.x && vP.y==vP2.y && vP.z==vP2.z &&
     648           0 :                     vN.x==vN2.x && vN.y==vN2.y && vN.z==vN2.z &&
     649           0 :                     vT.x==vT2.x && vT.y==vT2.y && vT.z==vT2.z)
     650             :                     bNotFound = TFALSE;
     651             :                 else
     652           0 :                     ++l2;
     653             :             }
     654             :             
     655             :             // merge if previously found
     656           0 :             if (!bNotFound)
     657           0 :                 piTriList_in_and_out[i] = piTriList_in_and_out[i2rec];
     658             :         }
     659             :     }
     660             :     else
     661             :     {
     662             :         int iL=iL_in, iR=iR_in;
     663           0 :         assert((iR_in-iL_in)>0); // at least 2 entries
     664             : 
     665             :         // separate (by fSep) all points between iL_in and iR_in in pTmpVert[]
     666           0 :         while (iL < iR)
     667             :         {
     668             :             tbool bReadyLeftSwap = TFALSE, bReadyRightSwap = TFALSE;
     669           0 :             while ((!bReadyLeftSwap) && iL<iR)
     670             :             {
     671           0 :                 assert(iL>=iL_in && iL<=iR_in);
     672           0 :                 bReadyLeftSwap = !(pTmpVert[iL].vert[channel]<fSep);
     673           0 :                 if (!bReadyLeftSwap) ++iL;
     674             :             }
     675           0 :             while ((!bReadyRightSwap) && iL<iR)
     676             :             {
     677           0 :                 assert(iR>=iL_in && iR<=iR_in);
     678           0 :                 bReadyRightSwap = pTmpVert[iR].vert[channel]<fSep;
     679           0 :                 if (!bReadyRightSwap) --iR;
     680             :             }
     681           0 :             assert( (iL<iR) || !(bReadyLeftSwap && bReadyRightSwap) );
     682             : 
     683           0 :             if (bReadyLeftSwap && bReadyRightSwap)
     684             :             {
     685           0 :                 const STmpVert sTmp = pTmpVert[iL];
     686           0 :                 assert(iL<iR);
     687           0 :                 pTmpVert[iL] = pTmpVert[iR];
     688           0 :                 pTmpVert[iR] = sTmp;
     689           0 :                 ++iL; --iR;
     690             :             }
     691             :         }
     692             : 
     693           0 :         assert(iL==(iR+1) || (iL==iR));
     694           0 :         if (iL==iR)
     695             :         {
     696           0 :             const tbool bReadyRightSwap = pTmpVert[iR].vert[channel]<fSep;
     697           0 :             if (bReadyRightSwap) ++iL;
     698           0 :             else --iR;
     699             :         }
     700             : 
     701             :         // only need to weld when there is more than 1 instance of the (x,y,z)
     702           0 :         if (iL_in < iR)
     703           0 :             MergeVertsFast(piTriList_in_and_out, pTmpVert, pContext, iL_in, iR);    // weld all left of fSep
     704           0 :         if (iL < iR_in)
     705           0 :             MergeVertsFast(piTriList_in_and_out, pTmpVert, pContext, iL, iR_in);    // weld all right of (or equal to) fSep
     706             :     }
     707           0 : }
     708             : 
     709           0 : static void MergeVertsSlow(int piTriList_in_and_out[], const SMikkTSpaceContext * pContext, const int pTable[], const int iEntries)
     710             : {
     711             :     // this can be optimized further using a tree structure or more hashing.
     712           0 :     int e=0;
     713           0 :     for (e=0; e<iEntries; e++)
     714             :     {
     715           0 :         int i = pTable[e];
     716           0 :         const int index = piTriList_in_and_out[i];
     717           0 :         const SVec3 vP = GetPosition(pContext, index);
     718           0 :         const SVec3 vN = GetNormal(pContext, index);
     719           0 :         const SVec3 vT = GetTexCoord(pContext, index);
     720             : 
     721           0 :         tbool bNotFound = TTRUE;
     722           0 :         int e2=0, i2rec=-1;
     723           0 :         while (e2<e && bNotFound)
     724             :         {
     725           0 :             const int i2 = pTable[e2];
     726           0 :             const int index2 = piTriList_in_and_out[i2];
     727           0 :             const SVec3 vP2 = GetPosition(pContext, index2);
     728           0 :             const SVec3 vN2 = GetNormal(pContext, index2);
     729           0 :             const SVec3 vT2 = GetTexCoord(pContext, index2);
     730           0 :             i2rec = i2;
     731             : 
     732           0 :             if (veq(vP,vP2) && veq(vN,vN2) && veq(vT,vT2))
     733             :                 bNotFound = TFALSE;
     734             :             else
     735           0 :                 ++e2;
     736             :         }
     737             :         
     738             :         // merge if previously found
     739           0 :         if (!bNotFound)
     740           0 :             piTriList_in_and_out[i] = piTriList_in_and_out[i2rec];
     741             :     }
     742           0 : }
     743             : 
     744           0 : static void GenerateSharedVerticesIndexListSlow(int piTriList_in_and_out[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn)
     745             : {
     746           0 :     int iNumUniqueVerts = 0, t=0, i=0;
     747           0 :     for (t=0; t<iNrTrianglesIn; t++)
     748             :     {
     749           0 :         for (i=0; i<3; i++)
     750             :         {
     751           0 :             const int offs = t*3 + i;
     752           0 :             const int index = piTriList_in_and_out[offs];
     753             : 
     754           0 :             const SVec3 vP = GetPosition(pContext, index);
     755           0 :             const SVec3 vN = GetNormal(pContext, index);
     756           0 :             const SVec3 vT = GetTexCoord(pContext, index);
     757             : 
     758           0 :             tbool bFound = TFALSE;
     759           0 :             int t2=0, index2rec=-1;
     760           0 :             while (!bFound && t2<=t)
     761             :             {
     762             :                 int j=0;
     763           0 :                 while (!bFound && j<3)
     764             :                 {
     765           0 :                     const int index2 = piTriList_in_and_out[t2*3 + j];
     766           0 :                     const SVec3 vP2 = GetPosition(pContext, index2);
     767           0 :                     const SVec3 vN2 = GetNormal(pContext, index2);
     768           0 :                     const SVec3 vT2 = GetTexCoord(pContext, index2);
     769             :                     
     770           0 :                     if (veq(vP,vP2) && veq(vN,vN2) && veq(vT,vT2))
     771             :                         bFound = TTRUE;
     772             :                     else
     773           0 :                         ++j;
     774             :                 }
     775           0 :                 if (!bFound) ++t2;
     776             :             }
     777             : 
     778           0 :             assert(bFound);
     779             :             // if we found our own
     780           0 :             if (index2rec == index) { ++iNumUniqueVerts; }
     781             : 
     782           0 :             piTriList_in_and_out[offs] = index2rec;
     783             :         }
     784             :     }
     785           0 : }
     786             : 
     787           0 : static int GenerateInitialVerticesIndexList(STriInfo pTriInfos[], int piTriList_out[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn)
     788             : {
     789           0 :     int iTSpacesOffs = 0, f=0, t=0;
     790           0 :     int iDstTriIndex = 0;
     791           0 :     for (f=0; f<pContext->m_pInterface->m_getNumFaces(pContext); f++)
     792             :     {
     793           0 :         const int verts = pContext->m_pInterface->m_getNumVerticesOfFace(pContext, f);
     794           0 :         if (verts!=3 && verts!=4) continue;
     795             : 
     796           0 :         pTriInfos[iDstTriIndex].iOrgFaceNumber = f;
     797           0 :         pTriInfos[iDstTriIndex].iTSpacesOffs = iTSpacesOffs;
     798             : 
     799           0 :         if (verts==3)
     800             :         {
     801           0 :             unsigned char * pVerts = pTriInfos[iDstTriIndex].vert_num;
     802           0 :             pVerts[0]=0; pVerts[1]=1; pVerts[2]=2;
     803           0 :             piTriList_out[iDstTriIndex*3+0] = MakeIndex(f, 0);
     804           0 :             piTriList_out[iDstTriIndex*3+1] = MakeIndex(f, 1);
     805           0 :             piTriList_out[iDstTriIndex*3+2] = MakeIndex(f, 2);
     806           0 :             ++iDstTriIndex; // next
     807             :         }
     808             :         else
     809             :         {
     810           0 :             {
     811           0 :                 pTriInfos[iDstTriIndex+1].iOrgFaceNumber = f;
     812           0 :                 pTriInfos[iDstTriIndex+1].iTSpacesOffs = iTSpacesOffs;
     813             :             }
     814             : 
     815           0 :             {
     816             :                 // need an order independent way to evaluate
     817             :                 // tspace on quads. This is done by splitting
     818             :                 // along the shortest diagonal.
     819           0 :                 const int i0 = MakeIndex(f, 0);
     820           0 :                 const int i1 = MakeIndex(f, 1);
     821           0 :                 const int i2 = MakeIndex(f, 2);
     822           0 :                 const int i3 = MakeIndex(f, 3);
     823           0 :                 const SVec3 T0 = GetTexCoord(pContext, i0);
     824           0 :                 const SVec3 T1 = GetTexCoord(pContext, i1);
     825           0 :                 const SVec3 T2 = GetTexCoord(pContext, i2);
     826           0 :                 const SVec3 T3 = GetTexCoord(pContext, i3);
     827           0 :                 const float distSQ_02 = LengthSquared(vsub(T2,T0));
     828           0 :                 const float distSQ_13 = LengthSquared(vsub(T3,T1));
     829           0 :                 tbool bQuadDiagIs_02;
     830           0 :                 if (distSQ_02<distSQ_13)
     831             :                     bQuadDiagIs_02 = TTRUE;
     832           0 :                 else if(distSQ_13<distSQ_02)
     833             :                     bQuadDiagIs_02 = TFALSE;
     834             :                 else
     835             :                 {
     836           0 :                     const SVec3 P0 = GetPosition(pContext, i0);
     837           0 :                     const SVec3 P1 = GetPosition(pContext, i1);
     838           0 :                     const SVec3 P2 = GetPosition(pContext, i2);
     839           0 :                     const SVec3 P3 = GetPosition(pContext, i3);
     840           0 :                     const float distSQ_02 = LengthSquared(vsub(P2,P0));
     841           0 :                     const float distSQ_13 = LengthSquared(vsub(P3,P1));
     842             : 
     843           0 :                     bQuadDiagIs_02 = distSQ_13<distSQ_02 ? TFALSE : TTRUE;
     844             :                 }
     845             : 
     846           0 :                 if (bQuadDiagIs_02)
     847             :                 {
     848           0 :                     {
     849           0 :                         unsigned char * pVerts_A = pTriInfos[iDstTriIndex].vert_num;
     850           0 :                         pVerts_A[0]=0; pVerts_A[1]=1; pVerts_A[2]=2;
     851             :                     }
     852           0 :                     piTriList_out[iDstTriIndex*3+0] = i0;
     853           0 :                     piTriList_out[iDstTriIndex*3+1] = i1;
     854           0 :                     piTriList_out[iDstTriIndex*3+2] = i2;
     855           0 :                     ++iDstTriIndex; // next
     856           0 :                     {
     857           0 :                         unsigned char * pVerts_B = pTriInfos[iDstTriIndex].vert_num;
     858           0 :                         pVerts_B[0]=0; pVerts_B[1]=2; pVerts_B[2]=3;
     859             :                     }
     860           0 :                     piTriList_out[iDstTriIndex*3+0] = i0;
     861           0 :                     piTriList_out[iDstTriIndex*3+1] = i2;
     862           0 :                     piTriList_out[iDstTriIndex*3+2] = i3;
     863           0 :                     ++iDstTriIndex; // next
     864             :                 }
     865             :                 else
     866             :                 {
     867           0 :                     {
     868           0 :                         unsigned char * pVerts_A = pTriInfos[iDstTriIndex].vert_num;
     869           0 :                         pVerts_A[0]=0; pVerts_A[1]=1; pVerts_A[2]=3;
     870             :                     }
     871           0 :                     piTriList_out[iDstTriIndex*3+0] = i0;
     872           0 :                     piTriList_out[iDstTriIndex*3+1] = i1;
     873           0 :                     piTriList_out[iDstTriIndex*3+2] = i3;
     874           0 :                     ++iDstTriIndex; // next
     875           0 :                     {
     876           0 :                         unsigned char * pVerts_B = pTriInfos[iDstTriIndex].vert_num;
     877           0 :                         pVerts_B[0]=1; pVerts_B[1]=2; pVerts_B[2]=3;
     878             :                     }
     879           0 :                     piTriList_out[iDstTriIndex*3+0] = i1;
     880           0 :                     piTriList_out[iDstTriIndex*3+1] = i2;
     881           0 :                     piTriList_out[iDstTriIndex*3+2] = i3;
     882           0 :                     ++iDstTriIndex; // next
     883             :                 }
     884             :             }
     885             :         }
     886             : 
     887           0 :         iTSpacesOffs += verts;
     888           0 :         assert(iDstTriIndex<=iNrTrianglesIn);
     889             :     }
     890             : 
     891           0 :     for (t=0; t<iNrTrianglesIn; t++)
     892           0 :         pTriInfos[t].iFlag = 0;
     893             : 
     894             :     // return total amount of tspaces
     895           0 :     return iTSpacesOffs;
     896             : }
     897             : 
     898             : static SVec3 GetPosition(const SMikkTSpaceContext * pContext, const int index)
     899             : {
     900           0 :     int iF, iI;
     901           0 :     SVec3 res; float pos[3];
     902           0 :     IndexToData(&iF, &iI, index);
     903           0 :     pContext->m_pInterface->m_getPosition(pContext, pos, iF, iI);
     904           0 :     res.x=pos[0]; res.y=pos[1]; res.z=pos[2];
     905           0 :     return res;
     906             : }
     907             : 
     908             : static SVec3 GetNormal(const SMikkTSpaceContext * pContext, const int index)
     909             : {
     910           0 :     int iF, iI;
     911           0 :     SVec3 res; float norm[3];
     912           0 :     IndexToData(&iF, &iI, index);
     913           0 :     pContext->m_pInterface->m_getNormal(pContext, norm, iF, iI);
     914           0 :     res.x=norm[0]; res.y=norm[1]; res.z=norm[2];
     915           0 :     return res;
     916             : }
     917             : 
     918             : static SVec3 GetTexCoord(const SMikkTSpaceContext * pContext, const int index)
     919             : {
     920           0 :     int iF, iI;
     921           0 :     SVec3 res; float texc[2];
     922           0 :     IndexToData(&iF, &iI, index);
     923           0 :     pContext->m_pInterface->m_getTexCoord(pContext, texc, iF, iI);
     924           0 :     res.x=texc[0]; res.y=texc[1]; res.z=1.0f;
     925           0 :     return res;
     926             : }
     927             : 
     928             : /////////////////////////////////////////////////////////////////////////////////////////////////////
     929             : /////////////////////////////////////////////////////////////////////////////////////////////////////
     930             : 
     931             : typedef union
     932             : {
     933             :     struct
     934             :     {
     935             :         int i0, i1, f;
     936             :     };
     937             :     int array[3];
     938             : } SEdge;
     939             : 
     940             : static void BuildNeighborsFast(STriInfo pTriInfos[], SEdge * pEdges, const int piTriListIn[], const int iNrTrianglesIn);
     941             : static void BuildNeighborsSlow(STriInfo pTriInfos[], const int piTriListIn[], const int iNrTrianglesIn);
     942             : 
     943             : // returns the texture area times 2
     944           0 : static float CalcTexArea(const SMikkTSpaceContext * pContext, const int indices[])
     945             : {
     946           0 :     const SVec3 t1 = GetTexCoord(pContext, indices[0]);
     947           0 :     const SVec3 t2 = GetTexCoord(pContext, indices[1]);
     948           0 :     const SVec3 t3 = GetTexCoord(pContext, indices[2]);
     949             : 
     950           0 :     const float t21x = t2.x-t1.x;
     951           0 :     const float t21y = t2.y-t1.y;
     952           0 :     const float t31x = t3.x-t1.x;
     953           0 :     const float t31y = t3.y-t1.y;
     954             : 
     955           0 :     const float fSignedAreaSTx2 = t21x*t31y - t21y*t31x;
     956             : 
     957           0 :     return fSignedAreaSTx2<0 ? (-fSignedAreaSTx2) : fSignedAreaSTx2;
     958             : }
     959             : 
     960           0 : static void InitTriInfo(STriInfo pTriInfos[], const int piTriListIn[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn)
     961             : {
     962           0 :     int f=0, i=0, t=0;
     963             :     // pTriInfos[f].iFlag is cleared in GenerateInitialVerticesIndexList() which is called before this function.
     964             : 
     965             :     // generate neighbor info list
     966           0 :     for (f=0; f<iNrTrianglesIn; f++)
     967           0 :         for (i=0; i<3; i++)
     968             :         {
     969           0 :             pTriInfos[f].FaceNeighbors[i] = -1;
     970           0 :             pTriInfos[f].AssignedGroup[i] = NULL;
     971             : 
     972           0 :             pTriInfos[f].vOs.x=0.0f; pTriInfos[f].vOs.y=0.0f; pTriInfos[f].vOs.z=0.0f;
     973           0 :             pTriInfos[f].vOt.x=0.0f; pTriInfos[f].vOt.y=0.0f; pTriInfos[f].vOt.z=0.0f;
     974           0 :             pTriInfos[f].fMagS = 0;
     975           0 :             pTriInfos[f].fMagT = 0;
     976             : 
     977             :             // assumed bad
     978           0 :             pTriInfos[f].iFlag |= GROUP_WITH_ANY;
     979             :         }
     980             : 
     981             :     // evaluate first order derivatives
     982           0 :     for (f=0; f<iNrTrianglesIn; f++)
     983             :     {
     984             :         // initial values
     985           0 :         const SVec3 v1 = GetPosition(pContext, piTriListIn[f*3+0]);
     986           0 :         const SVec3 v2 = GetPosition(pContext, piTriListIn[f*3+1]);
     987           0 :         const SVec3 v3 = GetPosition(pContext, piTriListIn[f*3+2]);
     988           0 :         const SVec3 t1 = GetTexCoord(pContext, piTriListIn[f*3+0]);
     989           0 :         const SVec3 t2 = GetTexCoord(pContext, piTriListIn[f*3+1]);
     990           0 :         const SVec3 t3 = GetTexCoord(pContext, piTriListIn[f*3+2]);
     991             : 
     992           0 :         const float t21x = t2.x-t1.x;
     993           0 :         const float t21y = t2.y-t1.y;
     994           0 :         const float t31x = t3.x-t1.x;
     995           0 :         const float t31y = t3.y-t1.y;
     996           0 :         const SVec3 d1 = vsub(v2,v1);
     997           0 :         const SVec3 d2 = vsub(v3,v1);
     998             : 
     999           0 :         const float fSignedAreaSTx2 = t21x*t31y - t21y*t31x;
    1000             :         //assert(fSignedAreaSTx2!=0);
    1001           0 :         SVec3 vOs = vsub(vscale(t31y,d1), vscale(t21y,d2)); // eq 18
    1002           0 :         SVec3 vOt = vadd(vscale(-t31x,d1), vscale(t21x,d2)); // eq 19
    1003             : 
    1004           0 :         pTriInfos[f].iFlag |= (fSignedAreaSTx2>0 ? ORIENT_PRESERVING : 0);
    1005             : 
    1006           0 :         if ( NotZero(fSignedAreaSTx2) )
    1007             :         {
    1008           0 :             const float fAbsArea = fabsf(fSignedAreaSTx2);
    1009           0 :             const float fLenOs = Length(vOs);
    1010           0 :             const float fLenOt = Length(vOt);
    1011           0 :             const float fS = (pTriInfos[f].iFlag&ORIENT_PRESERVING)==0 ? (-1.0f) : 1.0f;
    1012           0 :             if ( NotZero(fLenOs) ) pTriInfos[f].vOs = vscale(fS/fLenOs, vOs);
    1013           0 :             if ( NotZero(fLenOt) ) pTriInfos[f].vOt = vscale(fS/fLenOt, vOt);
    1014             : 
    1015             :             // evaluate magnitudes prior to normalization of vOs and vOt
    1016           0 :             pTriInfos[f].fMagS = fLenOs / fAbsArea;
    1017           0 :             pTriInfos[f].fMagT = fLenOt / fAbsArea;
    1018             : 
    1019             :             // if this is a good triangle
    1020           0 :             if ( NotZero(pTriInfos[f].fMagS) && NotZero(pTriInfos[f].fMagT))
    1021           0 :                 pTriInfos[f].iFlag &= (~GROUP_WITH_ANY);
    1022             :         }
    1023             :     }
    1024             : 
    1025             :     // force otherwise healthy quads to a fixed orientation
    1026           0 :     while (t<(iNrTrianglesIn-1))
    1027             :     {
    1028           0 :         const int iFO_a = pTriInfos[t].iOrgFaceNumber;
    1029           0 :         const int iFO_b = pTriInfos[t+1].iOrgFaceNumber;
    1030           0 :         if (iFO_a==iFO_b)   // this is a quad
    1031             :         {
    1032           0 :             const tbool bIsDeg_a = (pTriInfos[t].iFlag&MARK_DEGENERATE)!=0 ? TTRUE : TFALSE;
    1033           0 :             const tbool bIsDeg_b = (pTriInfos[t+1].iFlag&MARK_DEGENERATE)!=0 ? TTRUE : TFALSE;
    1034             :             
    1035             :             // bad triangles should already have been removed by
    1036             :             // DegenPrologue(), but just in case check bIsDeg_a and bIsDeg_a are false
    1037           0 :             if ((bIsDeg_a||bIsDeg_b)==TFALSE)
    1038             :             {
    1039           0 :                 const tbool bOrientA = (pTriInfos[t].iFlag&ORIENT_PRESERVING)!=0 ? TTRUE : TFALSE;
    1040           0 :                 const tbool bOrientB = (pTriInfos[t+1].iFlag&ORIENT_PRESERVING)!=0 ? TTRUE : TFALSE;
    1041             :                 // if this happens the quad has extremely bad mapping!!
    1042           0 :                 if (bOrientA!=bOrientB)
    1043             :                 {
    1044             :                     //printf("found quad with bad mapping\n");
    1045           0 :                     tbool bChooseOrientFirstTri = TFALSE;
    1046           0 :                     if ((pTriInfos[t+1].iFlag&GROUP_WITH_ANY)!=0) bChooseOrientFirstTri = TTRUE;
    1047           0 :                     else if( CalcTexArea(pContext, &piTriListIn[t*3+0]) >= CalcTexArea(pContext, &piTriListIn[(t+1)*3+0]) )
    1048             :                         bChooseOrientFirstTri = TTRUE;
    1049             : 
    1050             :                     // force match
    1051             :                     {
    1052           0 :                         const int t0 = bChooseOrientFirstTri ? t : (t+1);
    1053           0 :                         const int t1 = bChooseOrientFirstTri ? (t+1) : t;
    1054           0 :                         pTriInfos[t1].iFlag &= (~ORIENT_PRESERVING);    // clear first
    1055           0 :                         pTriInfos[t1].iFlag |= (pTriInfos[t0].iFlag&ORIENT_PRESERVING); // copy bit
    1056             :                     }
    1057             :                 }
    1058             :             }
    1059           0 :             t += 2;
    1060             :         }
    1061             :         else
    1062           0 :             ++t;
    1063             :     }
    1064             :     
    1065             :     // match up edge pairs
    1066           0 :     {
    1067           0 :         SEdge * pEdges = (SEdge *) malloc(sizeof(SEdge)*iNrTrianglesIn*3);
    1068           0 :         if (pEdges==NULL)
    1069           0 :             BuildNeighborsSlow(pTriInfos, piTriListIn, iNrTrianglesIn);
    1070             :         else
    1071             :         {
    1072           0 :             BuildNeighborsFast(pTriInfos, pEdges, piTriListIn, iNrTrianglesIn);
    1073             :     
    1074           0 :             free(pEdges);
    1075             :         }
    1076             :     }
    1077           0 : }
    1078             : 
    1079             : /////////////////////////////////////////////////////////////////////////////////////////////////////
    1080             : /////////////////////////////////////////////////////////////////////////////////////////////////////
    1081             : 
    1082             : static tbool AssignRecur(const int piTriListIn[], STriInfo psTriInfos[], const int iMyTriIndex, SGroup * pGroup);
    1083             : static void AddTriToGroup(SGroup * pGroup, const int iTriIndex);
    1084             : 
    1085           0 : static int Build4RuleGroups(STriInfo pTriInfos[], SGroup pGroups[], int piGroupTrianglesBuffer[], const int piTriListIn[], const int iNrTrianglesIn)
    1086             : {
    1087           0 :     const int iNrMaxGroups = iNrTrianglesIn*3;
    1088           0 :     int iNrActiveGroups = 0;
    1089           0 :     int iOffset = 0, f=0, i=0;
    1090           0 :     for (f=0; f<iNrTrianglesIn; f++)
    1091             :     {
    1092           0 :         for (i=0; i<3; i++)
    1093             :         {
    1094             :             // if not assigned to a group
    1095           0 :             if ((pTriInfos[f].iFlag&GROUP_WITH_ANY)==0 && pTriInfos[f].AssignedGroup[i]==NULL)
    1096             :             {
    1097           0 :                 tbool bOrPre;
    1098           0 :                 int neigh_indexL, neigh_indexR;
    1099           0 :                 const int vert_index = piTriListIn[f*3+i];
    1100           0 :                 assert(iNrActiveGroups<iNrMaxGroups);
    1101           0 :                 pTriInfos[f].AssignedGroup[i] = &pGroups[iNrActiveGroups];
    1102           0 :                 pTriInfos[f].AssignedGroup[i]->iVertexRepresentitive = vert_index;
    1103           0 :                 pTriInfos[f].AssignedGroup[i]->bOrientPreservering = (pTriInfos[f].iFlag&ORIENT_PRESERVING)!=0;
    1104           0 :                 pTriInfos[f].AssignedGroup[i]->iNrFaces = 0;
    1105           0 :                 pTriInfos[f].AssignedGroup[i]->pFaceIndices = &piGroupTrianglesBuffer[iOffset];
    1106           0 :                 ++iNrActiveGroups;
    1107             : 
    1108           0 :                 AddTriToGroup(pTriInfos[f].AssignedGroup[i], f);
    1109           0 :                 bOrPre = (pTriInfos[f].iFlag&ORIENT_PRESERVING)!=0 ? TTRUE : TFALSE;
    1110           0 :                 neigh_indexL = pTriInfos[f].FaceNeighbors[i];
    1111           0 :                 neigh_indexR = pTriInfos[f].FaceNeighbors[i>0?(i-1):2];
    1112           0 :                 if (neigh_indexL>=0) // neighbor
    1113             :                 {
    1114           0 :                     const tbool bAnswer =
    1115           0 :                         AssignRecur(piTriListIn, pTriInfos, neigh_indexL,
    1116             :                                     pTriInfos[f].AssignedGroup[i] );
    1117             :                     
    1118           0 :                     const tbool bOrPre2 = (pTriInfos[neigh_indexL].iFlag&ORIENT_PRESERVING)!=0 ? TTRUE : TFALSE;
    1119           0 :                     const tbool bDiff = bOrPre!=bOrPre2 ? TTRUE : TFALSE;
    1120             :                     assert(bAnswer || bDiff);
    1121             :                 }
    1122           0 :                 if (neigh_indexR>=0) // neighbor
    1123             :                 {
    1124           0 :                     const tbool bAnswer =
    1125           0 :                         AssignRecur(piTriListIn, pTriInfos, neigh_indexR,
    1126             :                                     pTriInfos[f].AssignedGroup[i] );
    1127             : 
    1128           0 :                     const tbool bOrPre2 = (pTriInfos[neigh_indexR].iFlag&ORIENT_PRESERVING)!=0 ? TTRUE : TFALSE;
    1129           0 :                     const tbool bDiff = bOrPre!=bOrPre2 ? TTRUE : TFALSE;
    1130             :                     assert(bAnswer || bDiff);
    1131             :                 }
    1132             : 
    1133             :                 // update offset
    1134           0 :                 iOffset += pTriInfos[f].AssignedGroup[i]->iNrFaces;
    1135             :                 // since the groups are disjoint a triangle can never
    1136             :                 // belong to more than 3 groups. Subsequently something
    1137             :                 // is completely screwed if this assertion ever hits.
    1138           0 :                 assert(iOffset <= iNrMaxGroups);
    1139             :             }
    1140             :         }
    1141             :     }
    1142             : 
    1143           0 :     return iNrActiveGroups;
    1144             : }
    1145             : 
    1146           0 : static void AddTriToGroup(SGroup * pGroup, const int iTriIndex)
    1147             : {
    1148           0 :     pGroup->pFaceIndices[pGroup->iNrFaces] = iTriIndex;
    1149           0 :     ++pGroup->iNrFaces;
    1150           0 : }
    1151             : 
    1152           0 : static tbool AssignRecur(const int piTriListIn[], STriInfo psTriInfos[],
    1153             :                  const int iMyTriIndex, SGroup * pGroup)
    1154             : {
    1155           0 :     STriInfo * pMyTriInfo = &psTriInfos[iMyTriIndex];
    1156             : 
    1157             :     // track down vertex
    1158           0 :     const int iVertRep = pGroup->iVertexRepresentitive;
    1159           0 :     const int * pVerts = &piTriListIn[3*iMyTriIndex+0];
    1160           0 :     int i=-1;
    1161           0 :     if (pVerts[0]==iVertRep) i=0;
    1162           0 :     else if(pVerts[1]==iVertRep) i=1;
    1163           0 :     else if(pVerts[2]==iVertRep) i=2;
    1164           0 :     assert(i>=0 && i<3);
    1165             : 
    1166             :     // early out
    1167           0 :     if (pMyTriInfo->AssignedGroup[i] == pGroup) return TTRUE;
    1168           0 :     else if(pMyTriInfo->AssignedGroup[i]!=NULL) return TFALSE;
    1169           0 :     if ((pMyTriInfo->iFlag&GROUP_WITH_ANY)!=0)
    1170             :     {
    1171             :         // first to group with a group-with-anything triangle
    1172             :         // determines it's orientation.
    1173             :         // This is the only existing order dependency in the code!!
    1174           0 :         if ( pMyTriInfo->AssignedGroup[0] == NULL &&
    1175           0 :             pMyTriInfo->AssignedGroup[1] == NULL &&
    1176           0 :             pMyTriInfo->AssignedGroup[2] == NULL )
    1177             :         {
    1178           0 :             pMyTriInfo->iFlag &= (~ORIENT_PRESERVING);
    1179           0 :             pMyTriInfo->iFlag |= (pGroup->bOrientPreservering ? ORIENT_PRESERVING : 0);
    1180             :         }
    1181             :     }
    1182           0 :     {
    1183           0 :         const tbool bOrient = (pMyTriInfo->iFlag&ORIENT_PRESERVING)!=0 ? TTRUE : TFALSE;
    1184           0 :         if (bOrient != pGroup->bOrientPreservering) return TFALSE;
    1185             :     }
    1186             : 
    1187           0 :     AddTriToGroup(pGroup, iMyTriIndex);
    1188           0 :     pMyTriInfo->AssignedGroup[i] = pGroup;
    1189             : 
    1190           0 :     {
    1191           0 :         const int neigh_indexL = pMyTriInfo->FaceNeighbors[i];
    1192           0 :         const int neigh_indexR = pMyTriInfo->FaceNeighbors[i>0?(i-1):2];
    1193           0 :         if (neigh_indexL>=0)
    1194           0 :             AssignRecur(piTriListIn, psTriInfos, neigh_indexL, pGroup);
    1195           0 :         if (neigh_indexR>=0)
    1196           0 :             AssignRecur(piTriListIn, psTriInfos, neigh_indexR, pGroup);
    1197             :     }
    1198             : 
    1199             : 
    1200             : 
    1201             :     return TTRUE;
    1202             : }
    1203             : 
    1204             : /////////////////////////////////////////////////////////////////////////////////////////////////////
    1205             : /////////////////////////////////////////////////////////////////////////////////////////////////////
    1206             : 
    1207             : static tbool CompareSubGroups(const SSubGroup * pg1, const SSubGroup * pg2);
    1208             : static void QuickSort(int* pSortBuffer, int iLeft, int iRight, unsigned int uSeed);
    1209             : static STSpace EvalTspace(int face_indices[], const int iFaces, const int piTriListIn[], const STriInfo pTriInfos[], const SMikkTSpaceContext * pContext, const int iVertexRepresentitive);
    1210             : 
    1211           0 : static tbool GenerateTSpaces(STSpace psTspace[], const STriInfo pTriInfos[], const SGroup pGroups[],
    1212             :                              const int iNrActiveGroups, const int piTriListIn[], const float fThresCos,
    1213             :                              const SMikkTSpaceContext * pContext)
    1214             : {
    1215           0 :     STSpace * pSubGroupTspace = NULL;
    1216           0 :     SSubGroup * pUniSubGroups = NULL;
    1217           0 :     int * pTmpMembers = NULL;
    1218           0 :     int iMaxNrFaces=0, iUniqueTspaces=0, g=0, i=0;
    1219           0 :     for (g=0; g<iNrActiveGroups; g++)
    1220           0 :         if (iMaxNrFaces < pGroups[g].iNrFaces)
    1221           0 :             iMaxNrFaces = pGroups[g].iNrFaces;
    1222             : 
    1223           0 :     if (iMaxNrFaces == 0) return TTRUE;
    1224             : 
    1225             :     // make initial allocations
    1226           0 :     pSubGroupTspace = (STSpace *) malloc(sizeof(STSpace)*iMaxNrFaces);
    1227           0 :     pUniSubGroups = (SSubGroup *) malloc(sizeof(SSubGroup)*iMaxNrFaces);
    1228           0 :     pTmpMembers = (int *) malloc(sizeof(int)*iMaxNrFaces);
    1229           0 :     if (pSubGroupTspace==NULL || pUniSubGroups==NULL || pTmpMembers==NULL)
    1230             :     {
    1231           0 :         if (pSubGroupTspace!=NULL) free(pSubGroupTspace);
    1232           0 :         if (pUniSubGroups!=NULL) free(pUniSubGroups);
    1233           0 :         if (pTmpMembers!=NULL) free(pTmpMembers);
    1234           0 :         return TFALSE;
    1235             :     }
    1236             : 
    1237             : 
    1238             :     iUniqueTspaces = 0;
    1239           0 :     for (g=0; g<iNrActiveGroups; g++)
    1240             :     {
    1241           0 :         const SGroup * pGroup = &pGroups[g];
    1242           0 :         int iUniqueSubGroups = 0, s=0;
    1243             : 
    1244           0 :         for (i=0; i<pGroup->iNrFaces; i++)    // triangles
    1245             :         {
    1246           0 :             const int f = pGroup->pFaceIndices[i];   // triangle number
    1247           0 :             int index=-1, iVertIndex=-1, iOF_1=-1, iMembers=0, j=0, l=0;
    1248           0 :             SSubGroup tmp_group;
    1249           0 :             tbool bFound;
    1250           0 :             SVec3 n, vOs, vOt;
    1251           0 :             if (pTriInfos[f].AssignedGroup[0]==pGroup) index=0;
    1252           0 :             else if(pTriInfos[f].AssignedGroup[1]==pGroup) index=1;
    1253           0 :             else if(pTriInfos[f].AssignedGroup[2]==pGroup) index=2;
    1254           0 :             assert(index>=0 && index<3);
    1255             : 
    1256           0 :             iVertIndex = piTriListIn[f*3+index];
    1257           0 :             assert(iVertIndex==pGroup->iVertexRepresentitive);
    1258             : 
    1259             :             // is normalized already
    1260           0 :             n = GetNormal(pContext, iVertIndex);
    1261             :             
    1262             :             // project
    1263           0 :             vOs = vsub(pTriInfos[f].vOs, vscale(vdot(n,pTriInfos[f].vOs), n));
    1264           0 :             vOt = vsub(pTriInfos[f].vOt, vscale(vdot(n,pTriInfos[f].vOt), n));
    1265           0 :             if ( VNotZero(vOs) ) vOs = Normalize(vOs);
    1266           0 :             if ( VNotZero(vOt) ) vOt = Normalize(vOt);
    1267             : 
    1268             :             // original face number
    1269           0 :             iOF_1 = pTriInfos[f].iOrgFaceNumber;
    1270             :             
    1271           0 :             iMembers = 0;
    1272           0 :             for (j=0; j<pGroup->iNrFaces; j++)
    1273             :             {
    1274           0 :                 const int t = pGroup->pFaceIndices[j];   // triangle number
    1275           0 :                 const int iOF_2 = pTriInfos[t].iOrgFaceNumber;
    1276             : 
    1277             :                 // project
    1278           0 :                 SVec3 vOs2 = vsub(pTriInfos[t].vOs, vscale(vdot(n,pTriInfos[t].vOs), n));
    1279           0 :                 SVec3 vOt2 = vsub(pTriInfos[t].vOt, vscale(vdot(n,pTriInfos[t].vOt), n));
    1280           0 :                 if ( VNotZero(vOs2) ) vOs2 = Normalize(vOs2);
    1281           0 :                 if ( VNotZero(vOt2) ) vOt2 = Normalize(vOt2);
    1282             : 
    1283           0 :                 {
    1284           0 :                     const tbool bAny = ( (pTriInfos[f].iFlag | pTriInfos[t].iFlag) & GROUP_WITH_ANY )!=0 ? TTRUE : TFALSE;
    1285             :                     // make sure triangles which belong to the same quad are joined.
    1286           0 :                     const tbool bSameOrgFace = iOF_1==iOF_2 ? TTRUE : TFALSE;
    1287             : 
    1288           0 :                     const float fCosS = vdot(vOs,vOs2);
    1289           0 :                     const float fCosT = vdot(vOt,vOt2);
    1290             : 
    1291           0 :                     assert(f!=t || bSameOrgFace);   // sanity check
    1292           0 :                     if (bAny || bSameOrgFace || (fCosS>fThresCos && fCosT>fThresCos))
    1293           0 :                         pTmpMembers[iMembers++] = t;
    1294             :                 }
    1295             :             }
    1296             : 
    1297             :             // sort pTmpMembers
    1298           0 :             tmp_group.iNrFaces = iMembers;
    1299           0 :             tmp_group.pTriMembers = pTmpMembers;
    1300           0 :             if (iMembers>1)
    1301             :             {
    1302           0 :                 unsigned int uSeed = INTERNAL_RND_SORT_SEED;    // could replace with a random seed?
    1303           0 :                 QuickSort(pTmpMembers, 0, iMembers-1, uSeed);
    1304             :             }
    1305             : 
    1306             :             // look for an existing match
    1307             :             bFound = TFALSE;
    1308             :             l=0;
    1309           0 :             while (l<iUniqueSubGroups && !bFound)
    1310             :             {
    1311           0 :                 bFound = CompareSubGroups(&tmp_group, &pUniSubGroups[l]);
    1312           0 :                 if (!bFound) ++l;
    1313             :             }
    1314             :             
    1315             :             // assign tangent space index
    1316           0 :             assert(bFound || l==iUniqueSubGroups);
    1317             :             //piTempTangIndices[f*3+index] = iUniqueTspaces+l;
    1318             : 
    1319             :             // if no match was found we allocate a new subgroup
    1320           0 :             if (!bFound)
    1321             :             {
    1322             :                 // insert new subgroup
    1323           0 :                 int * pIndices = (int *) malloc(sizeof(int)*iMembers);
    1324           0 :                 if (pIndices==NULL)
    1325             :                 {
    1326             :                     // clean up and return false
    1327             :                     int s=0;
    1328           0 :                     for (s=0; s<iUniqueSubGroups; s++)
    1329           0 :                         free(pUniSubGroups[s].pTriMembers);
    1330           0 :                     free(pUniSubGroups);
    1331           0 :                     free(pTmpMembers);
    1332           0 :                     free(pSubGroupTspace);
    1333           0 :                     return TFALSE;
    1334             :                 }
    1335           0 :                 pUniSubGroups[iUniqueSubGroups].iNrFaces = iMembers;
    1336           0 :                 pUniSubGroups[iUniqueSubGroups].pTriMembers = pIndices;
    1337           0 :                 memcpy(pIndices, tmp_group.pTriMembers, iMembers*sizeof(int));
    1338           0 :                 pSubGroupTspace[iUniqueSubGroups] =
    1339           0 :                     EvalTspace(tmp_group.pTriMembers, iMembers, piTriListIn, pTriInfos, pContext, pGroup->iVertexRepresentitive);
    1340           0 :                 ++iUniqueSubGroups;
    1341             :             }
    1342             : 
    1343             :             // output tspace
    1344           0 :             {
    1345           0 :                 const int iOffs = pTriInfos[f].iTSpacesOffs;
    1346           0 :                 const int iVert = pTriInfos[f].vert_num[index];
    1347           0 :                 STSpace * pTS_out = &psTspace[iOffs+iVert];
    1348           0 :                 assert(pTS_out->iCounter<2);
    1349           0 :                 assert(((pTriInfos[f].iFlag&ORIENT_PRESERVING)!=0) == pGroup->bOrientPreservering);
    1350           0 :                 if (pTS_out->iCounter==1)
    1351             :                 {
    1352           0 :                     *pTS_out = AvgTSpace(pTS_out, &pSubGroupTspace[l]);
    1353           0 :                     pTS_out->iCounter = 2;   // update counter
    1354           0 :                     pTS_out->bOrient = pGroup->bOrientPreservering;
    1355             :                 }
    1356             :                 else
    1357             :                 {
    1358           0 :                     assert(pTS_out->iCounter==0);
    1359           0 :                     *pTS_out = pSubGroupTspace[l];
    1360           0 :                     pTS_out->iCounter = 1;   // update counter
    1361           0 :                     pTS_out->bOrient = pGroup->bOrientPreservering;
    1362             :                 }
    1363             :             }
    1364             :         }
    1365             : 
    1366             :         // clean up and offset iUniqueTspaces
    1367           0 :         for (s=0; s<iUniqueSubGroups; s++)
    1368           0 :             free(pUniSubGroups[s].pTriMembers);
    1369           0 :         iUniqueTspaces += iUniqueSubGroups;
    1370             :     }
    1371             : 
    1372             :     // clean up
    1373           0 :     free(pUniSubGroups);
    1374           0 :     free(pTmpMembers);
    1375           0 :     free(pSubGroupTspace);
    1376             : 
    1377           0 :     return TTRUE;
    1378             : }
    1379             : 
    1380           0 : static STSpace EvalTspace(int face_indices[], const int iFaces, const int piTriListIn[], const STriInfo pTriInfos[],
    1381             :                           const SMikkTSpaceContext * pContext, const int iVertexRepresentitive)
    1382             : {
    1383           0 :     STSpace res;
    1384           0 :     float fAngleSum = 0;
    1385           0 :     int face=0;
    1386           0 :     res.vOs.x=0.0f; res.vOs.y=0.0f; res.vOs.z=0.0f;
    1387           0 :     res.vOt.x=0.0f; res.vOt.y=0.0f; res.vOt.z=0.0f;
    1388           0 :     res.fMagS = 0; res.fMagT = 0;
    1389             : 
    1390           0 :     for (face=0; face<iFaces; face++)
    1391             :     {
    1392           0 :         const int f = face_indices[face];
    1393             : 
    1394             :         // only valid triangles get to add their contribution
    1395           0 :         if ( (pTriInfos[f].iFlag&GROUP_WITH_ANY)==0 )
    1396             :         {
    1397           0 :             SVec3 n, vOs, vOt, p0, p1, p2, v1, v2;
    1398           0 :             float fCos, fAngle, fMagS, fMagT;
    1399           0 :             int i=-1, index=-1, i0=-1, i1=-1, i2=-1;
    1400           0 :             if (piTriListIn[3*f+0]==iVertexRepresentitive) i=0;
    1401           0 :             else if(piTriListIn[3*f+1]==iVertexRepresentitive) i=1;
    1402           0 :             else if(piTriListIn[3*f+2]==iVertexRepresentitive) i=2;
    1403           0 :             assert(i>=0 && i<3);
    1404             : 
    1405             :             // project
    1406           0 :             index = piTriListIn[3*f+i];
    1407           0 :             n = GetNormal(pContext, index);
    1408           0 :             vOs = vsub(pTriInfos[f].vOs, vscale(vdot(n,pTriInfos[f].vOs), n));
    1409           0 :             vOt = vsub(pTriInfos[f].vOt, vscale(vdot(n,pTriInfos[f].vOt), n));
    1410           0 :             if ( VNotZero(vOs) ) vOs = Normalize(vOs);
    1411           0 :             if ( VNotZero(vOt) ) vOt = Normalize(vOt);
    1412             : 
    1413           0 :             i2 = piTriListIn[3*f + (i<2?(i+1):0)];
    1414           0 :             i1 = piTriListIn[3*f + i];
    1415           0 :             i0 = piTriListIn[3*f + (i>0?(i-1):2)];
    1416             : 
    1417           0 :             p0 = GetPosition(pContext, i0);
    1418           0 :             p1 = GetPosition(pContext, i1);
    1419           0 :             p2 = GetPosition(pContext, i2);
    1420           0 :             v1 = vsub(p0,p1);
    1421           0 :             v2 = vsub(p2,p1);
    1422             : 
    1423             :             // project
    1424           0 :             v1 = vsub(v1, vscale(vdot(n,v1),n)); if( VNotZero(v1) ) v1 = Normalize(v1);
    1425           0 :             v2 = vsub(v2, vscale(vdot(n,v2),n)); if( VNotZero(v2) ) v2 = Normalize(v2);
    1426             : 
    1427             :             // weight contribution by the angle
    1428             :             // between the two edge vectors
    1429           0 :             fCos = vdot(v1,v2); fCos=fCos>1?1:(fCos<(-1) ? (-1) : fCos);
    1430           0 :             fAngle = (float) acos(fCos);
    1431           0 :             fMagS = pTriInfos[f].fMagS;
    1432           0 :             fMagT = pTriInfos[f].fMagT;
    1433             : 
    1434           0 :             res.vOs=vadd(res.vOs, vscale(fAngle,vOs));
    1435           0 :             res.vOt=vadd(res.vOt,vscale(fAngle,vOt));
    1436           0 :             res.fMagS+=(fAngle*fMagS);
    1437           0 :             res.fMagT+=(fAngle*fMagT);
    1438           0 :             fAngleSum += fAngle;
    1439             :         }
    1440             :     }
    1441             : 
    1442             :     // normalize
    1443           0 :     if ( VNotZero(res.vOs) ) res.vOs = Normalize(res.vOs);
    1444           0 :     if ( VNotZero(res.vOt) ) res.vOt = Normalize(res.vOt);
    1445           0 :     if (fAngleSum>0)
    1446             :     {
    1447           0 :         res.fMagS /= fAngleSum;
    1448           0 :         res.fMagT /= fAngleSum;
    1449             :     }
    1450             : 
    1451           0 :     return res;
    1452             : }
    1453             : 
    1454           0 : static tbool CompareSubGroups(const SSubGroup * pg1, const SSubGroup * pg2)
    1455             : {
    1456           0 :     tbool bStillSame=TTRUE;
    1457           0 :     int i=0;
    1458           0 :     if (pg1->iNrFaces!=pg2->iNrFaces) return TFALSE;
    1459           0 :     while (i<pg1->iNrFaces && bStillSame)
    1460             :     {
    1461           0 :         bStillSame = pg1->pTriMembers[i]==pg2->pTriMembers[i] ? TTRUE : TFALSE;
    1462           0 :         if (bStillSame) ++i;
    1463             :     }
    1464             :     return bStillSame;
    1465             : }
    1466             : 
    1467           0 : static void QuickSort(int* pSortBuffer, int iLeft, int iRight, unsigned int uSeed)
    1468             : {
    1469           0 :     int iL, iR, n, index, iMid, iTmp;
    1470             : 
    1471             :     // Random
    1472           0 :     unsigned int t=uSeed&31;
    1473           0 :     t=(uSeed<<t)|(uSeed>>(32-t));
    1474           0 :     uSeed=uSeed+t+3;
    1475             :     // Random end
    1476             : 
    1477           0 :     iL=iLeft; iR=iRight;
    1478           0 :     n = (iR-iL)+1;
    1479           0 :     assert(n>=0);
    1480           0 :     index = (int) (uSeed%n);
    1481             : 
    1482           0 :     iMid=pSortBuffer[index + iL];
    1483             : 
    1484             : 
    1485           0 :     do
    1486             :     {
    1487           0 :         while (pSortBuffer[iL] < iMid)
    1488           0 :             ++iL;
    1489           0 :         while (pSortBuffer[iR] > iMid)
    1490           0 :             --iR;
    1491             : 
    1492           0 :         if (iL <= iR)
    1493             :         {
    1494           0 :             iTmp = pSortBuffer[iL];
    1495           0 :             pSortBuffer[iL] = pSortBuffer[iR];
    1496           0 :             pSortBuffer[iR] = iTmp;
    1497           0 :             ++iL; --iR;
    1498             :         }
    1499             :     }
    1500           0 :     while (iL <= iR);
    1501             : 
    1502           0 :     if (iLeft < iR)
    1503           0 :         QuickSort(pSortBuffer, iLeft, iR, uSeed);
    1504           0 :     if (iL < iRight)
    1505             :         QuickSort(pSortBuffer, iL, iRight, uSeed);
    1506           0 : }
    1507             : 
    1508             : /////////////////////////////////////////////////////////////////////////////////////////////
    1509             : /////////////////////////////////////////////////////////////////////////////////////////////
    1510             : 
    1511             : static void QuickSortEdges(SEdge * pSortBuffer, int iLeft, int iRight, const int channel, unsigned int uSeed);
    1512             : static void GetEdge(int * i0_out, int * i1_out, int * edgenum_out, const int indices[], const int i0_in, const int i1_in);
    1513             : 
    1514           0 : static void BuildNeighborsFast(STriInfo pTriInfos[], SEdge * pEdges, const int piTriListIn[], const int iNrTrianglesIn)
    1515             : {
    1516             :     // build array of edges
    1517           0 :     unsigned int uSeed = INTERNAL_RND_SORT_SEED;                // could replace with a random seed?
    1518           0 :     int iEntries=0, iCurStartIndex=-1, f=0, i=0;
    1519           0 :     for (f=0; f<iNrTrianglesIn; f++)
    1520           0 :         for (i=0; i<3; i++)
    1521             :         {
    1522           0 :             const int i0 = piTriListIn[f*3+i];
    1523           0 :             const int i1 = piTriListIn[f*3+(i<2?(i+1):0)];
    1524           0 :             pEdges[f*3+i].i0 = i0 < i1 ? i0 : i1;            // put minimum index in i0
    1525           0 :             pEdges[f*3+i].i1 = !(i0 < i1) ? i0 : i1;     // put maximum index in i1
    1526           0 :             pEdges[f*3+i].f = f;                            // record face number
    1527             :         }
    1528             : 
    1529             :     // sort over all edges by i0, this is the pricy one.
    1530           0 :     QuickSortEdges(pEdges, 0, iNrTrianglesIn*3-1, 0, uSeed);    // sort channel 0 which is i0
    1531             : 
    1532             :     // sub sort over i1, should be fast.
    1533             :     // could replace this with a 64 bit int sort over (i0,i1)
    1534             :     // with i0 as msb in the quicksort call above.
    1535           0 :     iEntries = iNrTrianglesIn*3;
    1536           0 :     iCurStartIndex = 0;
    1537           0 :     for (i=1; i<iEntries; i++)
    1538             :     {
    1539           0 :         if (pEdges[iCurStartIndex].i0 != pEdges[i].i0)
    1540             :         {
    1541           0 :             const int iL = iCurStartIndex;
    1542           0 :             const int iR = i-1;
    1543             :             //const int iElems = i-iL;
    1544           0 :             iCurStartIndex = i;
    1545           0 :             QuickSortEdges(pEdges, iL, iR, 1, uSeed);   // sort channel 1 which is i1
    1546             :         }
    1547             :     }
    1548             : 
    1549             :     // sub sort over f, which should be fast.
    1550             :     // this step is to remain compliant with BuildNeighborsSlow() when
    1551             :     // more than 2 triangles use the same edge (such as a butterfly topology).
    1552             :     iCurStartIndex = 0;
    1553           0 :     for (i=1; i<iEntries; i++)
    1554             :     {
    1555           0 :         if (pEdges[iCurStartIndex].i0 != pEdges[i].i0 || pEdges[iCurStartIndex].i1 != pEdges[i].i1)
    1556             :         {
    1557           0 :             const int iL = iCurStartIndex;
    1558           0 :             const int iR = i-1;
    1559             :             //const int iElems = i-iL;
    1560           0 :             iCurStartIndex = i;
    1561           0 :             QuickSortEdges(pEdges, iL, iR, 2, uSeed);   // sort channel 2 which is f
    1562             :         }
    1563             :     }
    1564             : 
    1565             :     // pair up, adjacent triangles
    1566           0 :     for (i=0; i<iEntries; i++)
    1567             :     {
    1568           0 :         const int i0=pEdges[i].i0;
    1569           0 :         const int i1=pEdges[i].i1;
    1570           0 :         const int f = pEdges[i].f;
    1571           0 :         tbool bUnassigned_A;
    1572             : 
    1573           0 :         int i0_A, i1_A;
    1574           0 :         int edgenum_A, edgenum_B=0; // 0,1 or 2
    1575           0 :         GetEdge(&i0_A, &i1_A, &edgenum_A, &piTriListIn[f*3], i0, i1);   // resolve index ordering and edge_num
    1576           0 :         bUnassigned_A = pTriInfos[f].FaceNeighbors[edgenum_A] == -1 ? TTRUE : TFALSE;
    1577             : 
    1578           0 :         if (bUnassigned_A)
    1579             :         {
    1580             :             // get true index ordering
    1581           0 :             int j=i+1, t;
    1582           0 :             tbool bNotFound = TTRUE;
    1583           0 :             while (j<iEntries && i0==pEdges[j].i0 && i1==pEdges[j].i1 && bNotFound)
    1584             :             {
    1585           0 :                 tbool bUnassigned_B;
    1586           0 :                 int i0_B, i1_B;
    1587           0 :                 t = pEdges[j].f;
    1588             :                 // flip i0_B and i1_B
    1589           0 :                 GetEdge(&i1_B, &i0_B, &edgenum_B, &piTriListIn[t*3], pEdges[j].i0, pEdges[j].i1);   // resolve index ordering and edge_num
    1590             :                 //assert(!(i0_A==i1_B && i1_A==i0_B));
    1591           0 :                 bUnassigned_B =  pTriInfos[t].FaceNeighbors[edgenum_B]==-1 ? TTRUE : TFALSE;
    1592           0 :                 if (i0_A==i0_B && i1_A==i1_B && bUnassigned_B)
    1593             :                     bNotFound = TFALSE;
    1594             :                 else
    1595           0 :                     ++j;
    1596             :             }
    1597             : 
    1598           0 :             if (!bNotFound)
    1599             :             {
    1600           0 :                 int t = pEdges[j].f;
    1601           0 :                 pTriInfos[f].FaceNeighbors[edgenum_A] = t;
    1602             :                 //assert(pTriInfos[t].FaceNeighbors[edgenum_B]==-1);
    1603           0 :                 pTriInfos[t].FaceNeighbors[edgenum_B] = f;
    1604             :             }
    1605             :         }
    1606             :     }
    1607           0 : }
    1608             : 
    1609           0 : static void BuildNeighborsSlow(STriInfo pTriInfos[], const int piTriListIn[], const int iNrTrianglesIn)
    1610             : {
    1611           0 :     int f=0, i=0;
    1612           0 :     for (f=0; f<iNrTrianglesIn; f++)
    1613             :     {
    1614           0 :         for (i=0; i<3; i++)
    1615             :         {
    1616             :             // if unassigned
    1617           0 :             if (pTriInfos[f].FaceNeighbors[i] == -1)
    1618             :             {
    1619           0 :                 const int i0_A = piTriListIn[f*3+i];
    1620           0 :                 const int i1_A = piTriListIn[f*3+(i<2?(i+1):0)];
    1621             : 
    1622             :                 // search for a neighbor
    1623           0 :                 tbool bFound = TFALSE;
    1624           0 :                 int t=0, j=0;
    1625           0 :                 while (!bFound && t<iNrTrianglesIn)
    1626             :                 {
    1627           0 :                     if (t!=f)
    1628             :                     {
    1629             :                         j=0;
    1630           0 :                         while (!bFound && j<3)
    1631             :                         {
    1632             :                             // in rev order
    1633           0 :                             const int i1_B = piTriListIn[t*3+j];
    1634           0 :                             const int i0_B = piTriListIn[t*3+(j<2?(j+1):0)];
    1635             :                             //assert(!(i0_A==i1_B && i1_A==i0_B));
    1636           0 :                             if (i0_A==i0_B && i1_A==i1_B)
    1637             :                                 bFound = TTRUE;
    1638             :                             else
    1639           0 :                                 ++j;
    1640             :                         }
    1641             :                     }
    1642             :                     
    1643           0 :                     if (!bFound) ++t;
    1644             :                 }
    1645             : 
    1646             :                 // assign neighbors
    1647           0 :                 if (bFound)
    1648             :                 {
    1649           0 :                     pTriInfos[f].FaceNeighbors[i] = t;
    1650             :                     //assert(pTriInfos[t].FaceNeighbors[j]==-1);
    1651           0 :                     pTriInfos[t].FaceNeighbors[j] = f;
    1652             :                 }
    1653             :             }
    1654             :         }
    1655             :     }
    1656           0 : }
    1657             : 
    1658           0 : static void QuickSortEdges(SEdge * pSortBuffer, int iLeft, int iRight, const int channel, unsigned int uSeed)
    1659             : {
    1660           0 :     unsigned int t;
    1661           0 :     int iL, iR, n, index, iMid;
    1662             : 
    1663             :     // early out
    1664           0 :     SEdge sTmp;
    1665           0 :     const int iElems = iRight-iLeft+1;
    1666           0 :     if (iElems<2) return;
    1667           0 :     else if(iElems==2)
    1668             :     {
    1669           0 :         if (pSortBuffer[iLeft].array[channel] > pSortBuffer[iRight].array[channel])
    1670             :         {
    1671           0 :             sTmp = pSortBuffer[iLeft];
    1672           0 :             pSortBuffer[iLeft] = pSortBuffer[iRight];
    1673           0 :             pSortBuffer[iRight] = sTmp;
    1674             :         }
    1675           0 :         return;
    1676             :     }
    1677             : 
    1678             :     // Random
    1679           0 :     t=uSeed&31;
    1680           0 :     t=(uSeed<<t)|(uSeed>>(32-t));
    1681           0 :     uSeed=uSeed+t+3;
    1682             :     // Random end
    1683             : 
    1684           0 :     iL=iLeft, iR=iRight;
    1685           0 :     n = (iR-iL)+1;
    1686           0 :     assert(n>=0);
    1687           0 :     index = (int) (uSeed%n);
    1688             : 
    1689           0 :     iMid=pSortBuffer[index + iL].array[channel];
    1690             : 
    1691           0 :     do
    1692             :     {
    1693           0 :         while (pSortBuffer[iL].array[channel] < iMid)
    1694           0 :             ++iL;
    1695           0 :         while (pSortBuffer[iR].array[channel] > iMid)
    1696           0 :             --iR;
    1697             : 
    1698           0 :         if (iL <= iR)
    1699             :         {
    1700           0 :             sTmp = pSortBuffer[iL];
    1701           0 :             pSortBuffer[iL] = pSortBuffer[iR];
    1702           0 :             pSortBuffer[iR] = sTmp;
    1703           0 :             ++iL; --iR;
    1704             :         }
    1705             :     }
    1706           0 :     while (iL <= iR);
    1707             : 
    1708           0 :     if (iLeft < iR)
    1709           0 :         QuickSortEdges(pSortBuffer, iLeft, iR, channel, uSeed);
    1710           0 :     if (iL < iRight)
    1711           0 :         QuickSortEdges(pSortBuffer, iL, iRight, channel, uSeed);
    1712             : }
    1713             : 
    1714             : // resolve ordering and edge number
    1715             : static void GetEdge(int * i0_out, int * i1_out, int * edgenum_out, const int indices[], const int i0_in, const int i1_in)
    1716             : {
    1717           0 :     *edgenum_out = -1;
    1718             :     
    1719             :     // test if first index is on the edge
    1720           0 :     if (indices[0]==i0_in || indices[0]==i1_in)
    1721             :     {
    1722             :         // test if second index is on the edge
    1723           0 :         if (indices[1]==i0_in || indices[1]==i1_in)
    1724             :         {
    1725             :             edgenum_out[0]=0;   // first edge
    1726             :             i0_out[0]=indices[0];
    1727             :             i1_out[0]=indices[1];
    1728             :         }
    1729             :         else
    1730             :         {
    1731           0 :             edgenum_out[0]=2;   // third edge
    1732           0 :             i0_out[0]=indices[2];
    1733           0 :             i1_out[0]=indices[0];
    1734             :         }
    1735             :     }
    1736             :     else
    1737             :     {
    1738             :         // only second and third index is on the edge
    1739           0 :         edgenum_out[0]=1;   // second edge
    1740           0 :         i0_out[0]=indices[1];
    1741           0 :         i1_out[0]=indices[2];
    1742             :     }
    1743             : }
    1744             : 
    1745             : 
    1746             : /////////////////////////////////////////////////////////////////////////////////////////////
    1747             : /////////////////////////////////// Degenerate triangles ////////////////////////////////////
    1748             : 
    1749           0 : static void DegenPrologue(STriInfo pTriInfos[], int piTriList_out[], const int iNrTrianglesIn, const int iTotTris)
    1750             : {
    1751           0 :     int iNextGoodTriangleSearchIndex=-1;
    1752           0 :     tbool bStillFindingGoodOnes;
    1753             : 
    1754             :     // locate quads with only one good triangle
    1755           0 :     int t=0;
    1756           0 :     while (t<(iTotTris-1))
    1757             :     {
    1758           0 :         const int iFO_a = pTriInfos[t].iOrgFaceNumber;
    1759           0 :         const int iFO_b = pTriInfos[t+1].iOrgFaceNumber;
    1760           0 :         if (iFO_a==iFO_b)   // this is a quad
    1761             :         {
    1762           0 :             const tbool bIsDeg_a = (pTriInfos[t].iFlag&MARK_DEGENERATE)!=0 ? TTRUE : TFALSE;
    1763           0 :             const tbool bIsDeg_b = (pTriInfos[t+1].iFlag&MARK_DEGENERATE)!=0 ? TTRUE : TFALSE;
    1764           0 :             if ((bIsDeg_a^bIsDeg_b)!=0)
    1765             :             {
    1766           0 :                 pTriInfos[t].iFlag |= QUAD_ONE_DEGEN_TRI;
    1767           0 :                 pTriInfos[t+1].iFlag |= QUAD_ONE_DEGEN_TRI;
    1768             :             }
    1769           0 :             t += 2;
    1770             :         }
    1771             :         else
    1772           0 :             ++t;
    1773             :     }
    1774             : 
    1775             :     // reorder list so all degen triangles are moved to the back
    1776             :     // without reordering the good triangles
    1777             :     iNextGoodTriangleSearchIndex = 1;
    1778             :     t=0;
    1779             :     bStillFindingGoodOnes = TTRUE;
    1780           0 :     while (t<iNrTrianglesIn && bStillFindingGoodOnes)
    1781             :     {
    1782           0 :         const tbool bIsGood = (pTriInfos[t].iFlag&MARK_DEGENERATE)==0 ? TTRUE : TFALSE;
    1783           0 :         if (bIsGood)
    1784             :         {
    1785           0 :             if (iNextGoodTriangleSearchIndex < (t+2))
    1786           0 :                 iNextGoodTriangleSearchIndex = t+2;
    1787             :         }
    1788             :         else
    1789             :         {
    1790             :             int t0, t1;
    1791             :             // search for the first good triangle.
    1792             :             tbool bJustADegenerate = TTRUE;
    1793           0 :             while (bJustADegenerate && iNextGoodTriangleSearchIndex<iTotTris)
    1794             :             {
    1795           0 :                 const tbool bIsGood = (pTriInfos[iNextGoodTriangleSearchIndex].iFlag&MARK_DEGENERATE)==0 ? TTRUE : TFALSE;
    1796           0 :                 if (bIsGood) bJustADegenerate=TFALSE;
    1797           0 :                 else ++iNextGoodTriangleSearchIndex;
    1798             :             }
    1799             : 
    1800           0 :             t0 = t;
    1801           0 :             t1 = iNextGoodTriangleSearchIndex;
    1802           0 :             ++iNextGoodTriangleSearchIndex;
    1803           0 :             assert(iNextGoodTriangleSearchIndex > (t+1));
    1804             : 
    1805             :             // swap triangle t0 and t1
    1806           0 :             if (!bJustADegenerate)
    1807             :             {
    1808             :                 int i=0;
    1809           0 :                 for (i=0; i<3; i++)
    1810             :                 {
    1811           0 :                     const int index = piTriList_out[t0*3+i];
    1812           0 :                     piTriList_out[t0*3+i] = piTriList_out[t1*3+i];
    1813           0 :                     piTriList_out[t1*3+i] = index;
    1814             :                 }
    1815           0 :                 {
    1816           0 :                     const STriInfo tri_info = pTriInfos[t0];
    1817           0 :                     pTriInfos[t0] = pTriInfos[t1];
    1818           0 :                     pTriInfos[t1] = tri_info;
    1819             :                 }
    1820             :             }
    1821             :             else
    1822             :                 bStillFindingGoodOnes = TFALSE; // this is not supposed to happen
    1823             :         }
    1824             : 
    1825           0 :         if (bStillFindingGoodOnes) ++t;
    1826             :     }
    1827             : 
    1828           0 :     assert(bStillFindingGoodOnes);  // code will still work.
    1829           0 :     assert(iNrTrianglesIn == t);
    1830           0 : }
    1831             : 
    1832           0 : static void DegenEpilogue(STSpace psTspace[], STriInfo pTriInfos[], int piTriListIn[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn, const int iTotTris)
    1833             : {
    1834           0 :     int t=0, i=0;
    1835             :     // deal with degenerate triangles
    1836             :     // punishment for degenerate triangles is O(N^2)
    1837           0 :     for (t=iNrTrianglesIn; t<iTotTris; t++)
    1838             :     {
    1839             :         // degenerate triangles on a quad with one good triangle are skipped
    1840             :         // here but processed in the next loop
    1841           0 :         const tbool bSkip = (pTriInfos[t].iFlag&QUAD_ONE_DEGEN_TRI)!=0 ? TTRUE : TFALSE;
    1842             : 
    1843           0 :         if (!bSkip)
    1844             :         {
    1845           0 :             for (i=0; i<3; i++)
    1846             :             {
    1847           0 :                 const int index1 = piTriListIn[t*3+i];
    1848             :                 // search through the good triangles
    1849           0 :                 tbool bNotFound = TTRUE;
    1850           0 :                 int j=0;
    1851           0 :                 while (bNotFound && j<(3*iNrTrianglesIn))
    1852             :                 {
    1853           0 :                     const int index2 = piTriListIn[j];
    1854           0 :                     if (index1==index2) bNotFound=TFALSE;
    1855           0 :                     else ++j;
    1856             :                 }
    1857             : 
    1858           0 :                 if (!bNotFound)
    1859             :                 {
    1860           0 :                     const int iTri = j/3;
    1861           0 :                     const int iVert = j%3;
    1862           0 :                     const int iSrcVert=pTriInfos[iTri].vert_num[iVert];
    1863           0 :                     const int iSrcOffs=pTriInfos[iTri].iTSpacesOffs;
    1864           0 :                     const int iDstVert=pTriInfos[t].vert_num[i];
    1865           0 :                     const int iDstOffs=pTriInfos[t].iTSpacesOffs;
    1866             :                     
    1867             :                     // copy tspace
    1868           0 :                     psTspace[iDstOffs+iDstVert] = psTspace[iSrcOffs+iSrcVert];
    1869             :                 }
    1870             :             }
    1871             :         }
    1872             :     }
    1873             : 
    1874             :     // deal with degenerate quads with one good triangle
    1875           0 :     for (t=0; t<iNrTrianglesIn; t++)
    1876             :     {
    1877             :         // this triangle belongs to a quad where the
    1878             :         // other triangle is degenerate
    1879           0 :         if ( (pTriInfos[t].iFlag&QUAD_ONE_DEGEN_TRI)!=0 )
    1880             :         {
    1881           0 :             SVec3 vDstP;
    1882           0 :             int iOrgF=-1, i=0;
    1883           0 :             tbool bNotFound;
    1884           0 :             unsigned char * pV = pTriInfos[t].vert_num;
    1885           0 :             int iFlag = (1<<pV[0]) | (1<<pV[1]) | (1<<pV[2]);
    1886           0 :             int iMissingIndex = 0;
    1887           0 :             if ((iFlag&2)==0) iMissingIndex=1;
    1888           0 :             else if((iFlag&4)==0) iMissingIndex=2;
    1889           0 :             else if((iFlag&8)==0) iMissingIndex=3;
    1890             : 
    1891           0 :             iOrgF = pTriInfos[t].iOrgFaceNumber;
    1892           0 :             vDstP = GetPosition(pContext, MakeIndex(iOrgF, iMissingIndex));
    1893           0 :             bNotFound = TTRUE;
    1894           0 :             i=0;
    1895           0 :             while (bNotFound && i<3)
    1896             :             {
    1897           0 :                 const int iVert = pV[i];
    1898           0 :                 const SVec3 vSrcP = GetPosition(pContext, MakeIndex(iOrgF, iVert));
    1899           0 :                 if (veq(vSrcP, vDstP)==TTRUE)
    1900             :                 {
    1901           0 :                     const int iOffs = pTriInfos[t].iTSpacesOffs;
    1902           0 :                     psTspace[iOffs+iMissingIndex] = psTspace[iOffs+iVert];
    1903           0 :                     bNotFound=TFALSE;
    1904             :                 }
    1905             :                 else
    1906           0 :                     ++i;
    1907             :             }
    1908             :             assert(!bNotFound);
    1909             :         }
    1910             :     }
    1911           0 : }

Generated by: LCOV version 1.13