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