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