Merge branch 'blender2.7'
[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 void GenerateSharedVerticesIndexListSlow(int piTriList_in_and_out[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn);
451
452 typedef unsigned int uint;
453
454 static uint float_as_uint(const float v)
455 {
456         return *((uint*)(&v));
457 }
458
459 #define HASH(x, y, z) (((x) * 73856093) ^ ((y) * 19349663) ^ ((z) * 83492791))
460 #define HASH_F(x, y, z) HASH(float_as_uint(x), float_as_uint(y), float_as_uint(z))
461
462 /* Sort comp and data based on comp.
463  * comp2 and data2 are used as temporary storage. */
464 static void radixsort_pair(uint *comp, int *data, uint *comp2, int *data2, int n)
465 {
466         int shift = 0;
467         for(int pass = 0; pass < 4; pass++, shift+=8) {
468                 int bins[257] = {0};
469                 /* Count number of elements per bin. */
470                 for(int i = 0; i < n; i++) {
471                         bins[((comp[i] >> shift) & 0xff) + 1]++;
472                 }
473                 /* Compute prefix sum to find position of each bin in the sorted array. */
474                 for(int i = 2; i < 256; i++) {
475                         bins[i] += bins[i-1];
476                 }
477                 /* Insert the elements in their correct location based on their bin. */
478                 for(int i = 0; i < n; i++) {
479                         int pos = bins[(comp[i] >> shift) & 0xff]++;
480                         comp2[pos] = comp[i];
481                         data2[pos] = data[i];
482                 }
483
484                 /* Swap arrays. */
485                 int  *tmpdata = data; data = data2; data2 = tmpdata;
486                 uint *tmpcomp = comp; comp = comp2; comp2 = tmpcomp;
487         }
488 }
489
490 /* Merge identical vertices.
491  * To find vertices with identical position, normal and texcoord, we calculate a hash of the 9 values.
492  * Then, by sorting based on that hash, identical elements (having identical hashes) will be moved next to each other.
493  * Since there might be hash collisions, the elements of each block are then compared with each other and duplicates
494  * are merged.
495  */
496 static void GenerateSharedVerticesIndexList(int piTriList_in_and_out[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn)
497 {
498         int numVertices = iNrTrianglesIn*3;
499
500         uint *hashes = (uint*) malloc(sizeof(uint)*numVertices);
501         int *indices = (int*) malloc(sizeof(int)*numVertices);
502         uint *temp_hashes = (uint*) malloc(sizeof(uint)*numVertices);
503         int *temp_indices = (int*) malloc(sizeof(int)*numVertices);
504
505         if(hashes == NULL || indices == NULL || temp_hashes == NULL || temp_indices == NULL) {
506                 free(hashes);
507                 free(indices);
508                 free(temp_hashes);
509                 free(temp_indices);
510
511                 GenerateSharedVerticesIndexListSlow(piTriList_in_and_out, pContext, iNrTrianglesIn);
512                 return;
513         }
514
515         for (int i = 0; i < numVertices; i++) {
516                 const int index = piTriList_in_and_out[i];
517
518                 const SVec3 vP = GetPosition(pContext, index);
519                 const uint hashP = HASH_F(vP.x, vP.y, vP.z);
520
521                 const SVec3 vN = GetNormal(pContext, index);
522                 const uint hashN = HASH_F(vN.x, vN.y, vN.z);
523
524                 const SVec3 vT = GetTexCoord(pContext, index);
525                 const uint hashT = HASH_F(vT.x, vT.y, vT.z);
526
527                 hashes[i] = HASH(hashP, hashN, hashT);
528                 indices[i] = i;
529         }
530
531         radixsort_pair(hashes, indices, temp_hashes, temp_indices, numVertices);
532
533         free(temp_hashes);
534         free(temp_indices);
535
536         /* Process blocks of vertices with the same hash.
537          * Vertices in the block might still be separate, but we know for sure that
538          * vertices in different blocks will never be identical. */
539         int blockstart = 0;
540         while (blockstart < numVertices) {
541                 /* Find end of this block (exclusive). */
542                 uint hash = hashes[blockstart];
543                 int blockend = blockstart+1;
544                 for(; blockend < numVertices; blockend++) {
545                         if(hashes[blockend] != hash) break;
546                 }
547
548                 for(int i = blockstart; i < blockend; i++) {
549                         int index1 = piTriList_in_and_out[indices[i]];
550                         const SVec3 vP = GetPosition(pContext, index1);
551                         const SVec3 vN = GetNormal(pContext, index1);
552                         const SVec3 vT = GetTexCoord(pContext, index1);
553                         for(int i2 = i+1; i2 < blockend; i2++) {
554                                 int index2 = piTriList_in_and_out[indices[i2]];
555                                 if(index1 == index2) continue;
556
557                                 if(veq(vP, GetPosition(pContext, index2)) &&
558                                    veq(vN, GetNormal(pContext, index2)) &&
559                                    veq(vT, GetTexCoord(pContext, index2)))
560                                 {
561                                         piTriList_in_and_out[indices[i2]] = index1;
562                                         /* Once i2>i has been identified as a duplicate, we can stop since any
563                                          * i3>i2>i that is a duplicate of i (and therefore also i2) will also be
564                                          * compared to i2 and therefore be identified there anyways. */
565                                         break;
566                                 }
567                         }
568                 }
569
570                 /* Advance to next block. */
571                 blockstart = blockend;
572         }
573
574         free(hashes);
575         free(indices);
576 }
577
578 static void GenerateSharedVerticesIndexListSlow(int piTriList_in_and_out[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn)
579 {
580         int iNumUniqueVerts = 0, t=0, i=0;
581         for (t=0; t<iNrTrianglesIn; t++)
582         {
583                 for (i=0; i<3; i++)
584                 {
585                         const int offs = t*3 + i;
586                         const int index = piTriList_in_and_out[offs];
587
588                         const SVec3 vP = GetPosition(pContext, index);
589                         const SVec3 vN = GetNormal(pContext, index);
590                         const SVec3 vT = GetTexCoord(pContext, index);
591
592                         tbool bFound = TFALSE;
593                         int t2=0, index2rec=-1;
594                         while (!bFound && t2<=t)
595                         {
596                                 int j=0;
597                                 while (!bFound && j<3)
598                                 {
599                                         const int index2 = piTriList_in_and_out[t2*3 + j];
600                                         const SVec3 vP2 = GetPosition(pContext, index2);
601                                         const SVec3 vN2 = GetNormal(pContext, index2);
602                                         const SVec3 vT2 = GetTexCoord(pContext, index2);
603                                         
604                                         if (veq(vP,vP2) && veq(vN,vN2) && veq(vT,vT2))
605                                                 bFound = TTRUE;
606                                         else
607                                                 ++j;
608                                 }
609                                 if (!bFound) ++t2;
610                         }
611
612                         assert(bFound);
613                         // if we found our own
614                         if (index2rec == index) { ++iNumUniqueVerts; }
615
616                         piTriList_in_and_out[offs] = index2rec;
617                 }
618         }
619 }
620
621 static int GenerateInitialVerticesIndexList(STriInfo pTriInfos[], int piTriList_out[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn)
622 {
623         int iTSpacesOffs = 0, f=0, t=0;
624         int iDstTriIndex = 0;
625         for (f=0; f<pContext->m_pInterface->m_getNumFaces(pContext); f++)
626         {
627                 const int verts = pContext->m_pInterface->m_getNumVerticesOfFace(pContext, f);
628                 if (verts!=3 && verts!=4) continue;
629
630                 pTriInfos[iDstTriIndex].iOrgFaceNumber = f;
631                 pTriInfos[iDstTriIndex].iTSpacesOffs = iTSpacesOffs;
632
633                 if (verts==3)
634                 {
635                         unsigned char * pVerts = pTriInfos[iDstTriIndex].vert_num;
636                         pVerts[0]=0; pVerts[1]=1; pVerts[2]=2;
637                         piTriList_out[iDstTriIndex*3+0] = MakeIndex(f, 0);
638                         piTriList_out[iDstTriIndex*3+1] = MakeIndex(f, 1);
639                         piTriList_out[iDstTriIndex*3+2] = MakeIndex(f, 2);
640                         ++iDstTriIndex; // next
641                 }
642                 else
643                 {
644                         {
645                                 pTriInfos[iDstTriIndex+1].iOrgFaceNumber = f;
646                                 pTriInfos[iDstTriIndex+1].iTSpacesOffs = iTSpacesOffs;
647                         }
648
649                         {
650                                 // need an order independent way to evaluate
651                                 // tspace on quads. This is done by splitting
652                                 // along the shortest diagonal.
653                                 const int i0 = MakeIndex(f, 0);
654                                 const int i1 = MakeIndex(f, 1);
655                                 const int i2 = MakeIndex(f, 2);
656                                 const int i3 = MakeIndex(f, 3);
657                                 const SVec3 T0 = GetTexCoord(pContext, i0);
658                                 const SVec3 T1 = GetTexCoord(pContext, i1);
659                                 const SVec3 T2 = GetTexCoord(pContext, i2);
660                                 const SVec3 T3 = GetTexCoord(pContext, i3);
661                                 const float distSQ_02 = LengthSquared(vsub(T2,T0));
662                                 const float distSQ_13 = LengthSquared(vsub(T3,T1));
663                                 tbool bQuadDiagIs_02;
664                                 if (distSQ_02<distSQ_13)
665                                         bQuadDiagIs_02 = TTRUE;
666                                 else if (distSQ_13<distSQ_02)
667                                         bQuadDiagIs_02 = TFALSE;
668                                 else
669                                 {
670                                         const SVec3 P0 = GetPosition(pContext, i0);
671                                         const SVec3 P1 = GetPosition(pContext, i1);
672                                         const SVec3 P2 = GetPosition(pContext, i2);
673                                         const SVec3 P3 = GetPosition(pContext, i3);
674                                         const float distSQ_02 = LengthSquared(vsub(P2,P0));
675                                         const float distSQ_13 = LengthSquared(vsub(P3,P1));
676
677                                         bQuadDiagIs_02 = distSQ_13<distSQ_02 ? TFALSE : TTRUE;
678                                 }
679
680                                 if (bQuadDiagIs_02)
681                                 {
682                                         {
683                                                 unsigned char * pVerts_A = pTriInfos[iDstTriIndex].vert_num;
684                                                 pVerts_A[0]=0; pVerts_A[1]=1; pVerts_A[2]=2;
685                                         }
686                                         piTriList_out[iDstTriIndex*3+0] = i0;
687                                         piTriList_out[iDstTriIndex*3+1] = i1;
688                                         piTriList_out[iDstTriIndex*3+2] = i2;
689                                         ++iDstTriIndex; // next
690                                         {
691                                                 unsigned char * pVerts_B = pTriInfos[iDstTriIndex].vert_num;
692                                                 pVerts_B[0]=0; pVerts_B[1]=2; pVerts_B[2]=3;
693                                         }
694                                         piTriList_out[iDstTriIndex*3+0] = i0;
695                                         piTriList_out[iDstTriIndex*3+1] = i2;
696                                         piTriList_out[iDstTriIndex*3+2] = i3;
697                                         ++iDstTriIndex; // next
698                                 }
699                                 else
700                                 {
701                                         {
702                                                 unsigned char * pVerts_A = pTriInfos[iDstTriIndex].vert_num;
703                                                 pVerts_A[0]=0; pVerts_A[1]=1; pVerts_A[2]=3;
704                                         }
705                                         piTriList_out[iDstTriIndex*3+0] = i0;
706                                         piTriList_out[iDstTriIndex*3+1] = i1;
707                                         piTriList_out[iDstTriIndex*3+2] = i3;
708                                         ++iDstTriIndex; // next
709                                         {
710                                                 unsigned char * pVerts_B = pTriInfos[iDstTriIndex].vert_num;
711                                                 pVerts_B[0]=1; pVerts_B[1]=2; pVerts_B[2]=3;
712                                         }
713                                         piTriList_out[iDstTriIndex*3+0] = i1;
714                                         piTriList_out[iDstTriIndex*3+1] = i2;
715                                         piTriList_out[iDstTriIndex*3+2] = i3;
716                                         ++iDstTriIndex; // next
717                                 }
718                         }
719                 }
720
721                 iTSpacesOffs += verts;
722                 assert(iDstTriIndex<=iNrTrianglesIn);
723         }
724
725         for (t=0; t<iNrTrianglesIn; t++)
726                 pTriInfos[t].iFlag = 0;
727
728         // return total amount of tspaces
729         return iTSpacesOffs;
730 }
731
732 MIKK_INLINE SVec3 GetPosition(const SMikkTSpaceContext * pContext, const int index)
733 {
734         int iF, iI;
735         SVec3 res; float pos[3];
736         IndexToData(&iF, &iI, index);
737         pContext->m_pInterface->m_getPosition(pContext, pos, iF, iI);
738         res.x=pos[0]; res.y=pos[1]; res.z=pos[2];
739         return res;
740 }
741
742 MIKK_INLINE SVec3 GetNormal(const SMikkTSpaceContext * pContext, const int index)
743 {
744         int iF, iI;
745         SVec3 res; float norm[3];
746         IndexToData(&iF, &iI, index);
747         pContext->m_pInterface->m_getNormal(pContext, norm, iF, iI);
748         res.x=norm[0]; res.y=norm[1]; res.z=norm[2];
749         return res;
750 }
751
752 MIKK_INLINE SVec3 GetTexCoord(const SMikkTSpaceContext * pContext, const int index)
753 {
754         int iF, iI;
755         SVec3 res; float texc[2];
756         IndexToData(&iF, &iI, index);
757         pContext->m_pInterface->m_getTexCoord(pContext, texc, iF, iI);
758         res.x=texc[0]; res.y=texc[1]; res.z=1.0f;
759         return res;
760 }
761
762 /////////////////////////////////////////////////////////////////////////////////////////////////////
763 /////////////////////////////////////////////////////////////////////////////////////////////////////
764
765 typedef union {
766         struct
767         {
768                 int i0, i1, f;
769         };
770         int array[3];
771 } SEdge;
772
773 static void BuildNeighborsFast(STriInfo pTriInfos[], SEdge * pEdges, const int piTriListIn[], const int iNrTrianglesIn);
774 static void BuildNeighborsSlow(STriInfo pTriInfos[], const int piTriListIn[], const int iNrTrianglesIn);
775
776 // returns the texture area times 2
777 static float CalcTexArea(const SMikkTSpaceContext * pContext, const int indices[])
778 {
779         const SVec3 t1 = GetTexCoord(pContext, indices[0]);
780         const SVec3 t2 = GetTexCoord(pContext, indices[1]);
781         const SVec3 t3 = GetTexCoord(pContext, indices[2]);
782
783         const float t21x = t2.x-t1.x;
784         const float t21y = t2.y-t1.y;
785         const float t31x = t3.x-t1.x;
786         const float t31y = t3.y-t1.y;
787
788         const float fSignedAreaSTx2 = t21x*t31y - t21y*t31x;
789
790         return fSignedAreaSTx2<0 ? (-fSignedAreaSTx2) : fSignedAreaSTx2;
791 }
792
793 static void InitTriInfo(STriInfo pTriInfos[], const int piTriListIn[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn)
794 {
795         int f=0, i=0, t=0;
796         // pTriInfos[f].iFlag is cleared in GenerateInitialVerticesIndexList() which is called before this function.
797
798         // generate neighbor info list
799         for (f=0; f<iNrTrianglesIn; f++)
800                 for (i=0; i<3; i++)
801                 {
802                         pTriInfos[f].FaceNeighbors[i] = -1;
803                         pTriInfos[f].AssignedGroup[i] = NULL;
804
805                         pTriInfos[f].vOs.x=0.0f; pTriInfos[f].vOs.y=0.0f; pTriInfos[f].vOs.z=0.0f;
806                         pTriInfos[f].vOt.x=0.0f; pTriInfos[f].vOt.y=0.0f; pTriInfos[f].vOt.z=0.0f;
807                         pTriInfos[f].fMagS = 0;
808                         pTriInfos[f].fMagT = 0;
809
810                         // assumed bad
811                         pTriInfos[f].iFlag |= GROUP_WITH_ANY;
812                 }
813
814         // evaluate first order derivatives
815         for (f=0; f<iNrTrianglesIn; f++)
816         {
817                 // initial values
818                 const SVec3 v1 = GetPosition(pContext, piTriListIn[f*3+0]);
819                 const SVec3 v2 = GetPosition(pContext, piTriListIn[f*3+1]);
820                 const SVec3 v3 = GetPosition(pContext, piTriListIn[f*3+2]);
821                 const SVec3 t1 = GetTexCoord(pContext, piTriListIn[f*3+0]);
822                 const SVec3 t2 = GetTexCoord(pContext, piTriListIn[f*3+1]);
823                 const SVec3 t3 = GetTexCoord(pContext, piTriListIn[f*3+2]);
824
825                 const float t21x = t2.x-t1.x;
826                 const float t21y = t2.y-t1.y;
827                 const float t31x = t3.x-t1.x;
828                 const float t31y = t3.y-t1.y;
829                 const SVec3 d1 = vsub(v2,v1);
830                 const SVec3 d2 = vsub(v3,v1);
831
832                 const float fSignedAreaSTx2 = t21x*t31y - t21y*t31x;
833                 //assert(fSignedAreaSTx2!=0);
834                 SVec3 vOs = vsub(vscale(t31y,d1), vscale(t21y,d2));     // eq 18
835                 SVec3 vOt = vadd(vscale(-t31x,d1), vscale(t21x,d2)); // eq 19
836
837                 pTriInfos[f].iFlag |= (fSignedAreaSTx2>0 ? ORIENT_PRESERVING : 0);
838
839                 if ( NotZero(fSignedAreaSTx2) )
840                 {
841                         const float fAbsArea = fabsf(fSignedAreaSTx2);
842                         const float fLenOs = Length(vOs);
843                         const float fLenOt = Length(vOt);
844                         const float fS = (pTriInfos[f].iFlag&ORIENT_PRESERVING)==0 ? (-1.0f) : 1.0f;
845                         if ( NotZero(fLenOs) ) pTriInfos[f].vOs = vscale(fS/fLenOs, vOs);
846                         if ( NotZero(fLenOt) ) pTriInfos[f].vOt = vscale(fS/fLenOt, vOt);
847
848                         // evaluate magnitudes prior to normalization of vOs and vOt
849                         pTriInfos[f].fMagS = fLenOs / fAbsArea;
850                         pTriInfos[f].fMagT = fLenOt / fAbsArea;
851
852                         // if this is a good triangle
853                         if ( NotZero(pTriInfos[f].fMagS) && NotZero(pTriInfos[f].fMagT))
854                                 pTriInfos[f].iFlag &= (~GROUP_WITH_ANY);
855                 }
856         }
857
858         // force otherwise healthy quads to a fixed orientation
859         while (t<(iNrTrianglesIn-1))
860         {
861                 const int iFO_a = pTriInfos[t].iOrgFaceNumber;
862                 const int iFO_b = pTriInfos[t+1].iOrgFaceNumber;
863                 if (iFO_a==iFO_b)       // this is a quad
864                 {
865                         const tbool bIsDeg_a = (pTriInfos[t].iFlag&MARK_DEGENERATE)!=0 ? TTRUE : TFALSE;
866                         const tbool bIsDeg_b = (pTriInfos[t+1].iFlag&MARK_DEGENERATE)!=0 ? TTRUE : TFALSE;
867                         
868                         // bad triangles should already have been removed by
869                         // DegenPrologue(), but just in case check bIsDeg_a and bIsDeg_a are false
870                         if ((bIsDeg_a||bIsDeg_b)==TFALSE)
871                         {
872                                 const tbool bOrientA = (pTriInfos[t].iFlag&ORIENT_PRESERVING)!=0 ? TTRUE : TFALSE;
873                                 const tbool bOrientB = (pTriInfos[t+1].iFlag&ORIENT_PRESERVING)!=0 ? TTRUE : TFALSE;
874                                 // if this happens the quad has extremely bad mapping!!
875                                 if (bOrientA!=bOrientB)
876                                 {
877                                         //printf("found quad with bad mapping\n");
878                                         tbool bChooseOrientFirstTri = TFALSE;
879                                         if ((pTriInfos[t+1].iFlag&GROUP_WITH_ANY)!=0) bChooseOrientFirstTri = TTRUE;
880                                         else if ( CalcTexArea(pContext, &piTriListIn[t*3+0]) >= CalcTexArea(pContext, &piTriListIn[(t+1)*3+0]) )
881                                                 bChooseOrientFirstTri = TTRUE;
882
883                                         // force match
884                                         {
885                                                 const int t0 = bChooseOrientFirstTri ? t : (t+1);
886                                                 const int t1 = bChooseOrientFirstTri ? (t+1) : t;
887                                                 pTriInfos[t1].iFlag &= (~ORIENT_PRESERVING);    // clear first
888                                                 pTriInfos[t1].iFlag |= (pTriInfos[t0].iFlag&ORIENT_PRESERVING); // copy bit
889                                         }
890                                 }
891                         }
892                         t += 2;
893                 }
894                 else
895                         ++t;
896         }
897         
898         // match up edge pairs
899         {
900                 SEdge * pEdges = (SEdge *) malloc(sizeof(SEdge[3])*iNrTrianglesIn);
901                 if (pEdges==NULL)
902                         BuildNeighborsSlow(pTriInfos, piTriListIn, iNrTrianglesIn);
903                 else
904                 {
905                         BuildNeighborsFast(pTriInfos, pEdges, piTriListIn, iNrTrianglesIn);
906         
907                         free(pEdges);
908                 }
909         }
910 }
911
912 /////////////////////////////////////////////////////////////////////////////////////////////////////
913 /////////////////////////////////////////////////////////////////////////////////////////////////////
914
915 static tbool AssignRecur(const int piTriListIn[], STriInfo psTriInfos[], const int iMyTriIndex, SGroup * pGroup);
916 MIKK_INLINE void AddTriToGroup(SGroup * pGroup, const int iTriIndex);
917
918 static int Build4RuleGroups(STriInfo pTriInfos[], SGroup pGroups[], int piGroupTrianglesBuffer[], const int piTriListIn[], const int iNrTrianglesIn)
919 {
920         const int iNrMaxGroups = iNrTrianglesIn*3;
921         int iNrActiveGroups = 0;
922         int iOffset = 0, f=0, i=0;
923         (void)iNrMaxGroups;  /* quiet warnings in non debug mode */
924         for (f=0; f<iNrTrianglesIn; f++)
925         {
926                 for (i=0; i<3; i++)
927                 {
928                         // if not assigned to a group
929                         if ((pTriInfos[f].iFlag&GROUP_WITH_ANY)==0 && pTriInfos[f].AssignedGroup[i]==NULL)
930                         {
931                                 tbool bOrPre;
932                                 int neigh_indexL, neigh_indexR;
933                                 const int vert_index = piTriListIn[f*3+i];
934                                 assert(iNrActiveGroups<iNrMaxGroups);
935                                 pTriInfos[f].AssignedGroup[i] = &pGroups[iNrActiveGroups];
936                                 pTriInfos[f].AssignedGroup[i]->iVertexRepresentitive = vert_index;
937                                 pTriInfos[f].AssignedGroup[i]->bOrientPreservering = (pTriInfos[f].iFlag&ORIENT_PRESERVING)!=0;
938                                 pTriInfos[f].AssignedGroup[i]->iNrFaces = 0;
939                                 pTriInfos[f].AssignedGroup[i]->pFaceIndices = &piGroupTrianglesBuffer[iOffset];
940                                 ++iNrActiveGroups;
941
942                                 AddTriToGroup(pTriInfos[f].AssignedGroup[i], f);
943                                 bOrPre = (pTriInfos[f].iFlag&ORIENT_PRESERVING)!=0 ? TTRUE : TFALSE;
944                                 neigh_indexL = pTriInfos[f].FaceNeighbors[i];
945                                 neigh_indexR = pTriInfos[f].FaceNeighbors[i>0?(i-1):2];
946                                 if (neigh_indexL>=0) // neighbor
947                                 {
948                                         const tbool bAnswer =
949                                                 AssignRecur(piTriListIn, pTriInfos, neigh_indexL,
950                                                                         pTriInfos[f].AssignedGroup[i] );
951                                         
952                                         const tbool bOrPre2 = (pTriInfos[neigh_indexL].iFlag&ORIENT_PRESERVING)!=0 ? TTRUE : TFALSE;
953                                         const tbool bDiff = bOrPre!=bOrPre2 ? TTRUE : TFALSE;
954                                         assert(bAnswer || bDiff);
955                                         (void)bAnswer, (void)bDiff;  /* quiet warnings in non debug mode */
956                                 }
957                                 if (neigh_indexR>=0) // neighbor
958                                 {
959                                         const tbool bAnswer =
960                                                 AssignRecur(piTriListIn, pTriInfos, neigh_indexR,
961                                                                         pTriInfos[f].AssignedGroup[i] );
962
963                                         const tbool bOrPre2 = (pTriInfos[neigh_indexR].iFlag&ORIENT_PRESERVING)!=0 ? TTRUE : TFALSE;
964                                         const tbool bDiff = bOrPre!=bOrPre2 ? TTRUE : TFALSE;
965                                         assert(bAnswer || bDiff);
966                                         (void)bAnswer, (void)bDiff;  /* quiet warnings in non debug mode */
967                                 }
968
969                                 // update offset
970                                 iOffset += pTriInfos[f].AssignedGroup[i]->iNrFaces;
971                                 // since the groups are disjoint a triangle can never
972                                 // belong to more than 3 groups. Subsequently something
973                                 // is completely screwed if this assertion ever hits.
974                                 assert(iOffset <= iNrMaxGroups);
975                         }
976                 }
977         }
978
979         return iNrActiveGroups;
980 }
981
982 MIKK_INLINE void AddTriToGroup(SGroup * pGroup, const int iTriIndex)
983 {
984         pGroup->pFaceIndices[pGroup->iNrFaces] = iTriIndex;
985         ++pGroup->iNrFaces;
986 }
987
988 static tbool AssignRecur(const int piTriListIn[], STriInfo psTriInfos[],
989                                  const int iMyTriIndex, SGroup * pGroup)
990 {
991         STriInfo * pMyTriInfo = &psTriInfos[iMyTriIndex];
992
993         // track down vertex
994         const int iVertRep = pGroup->iVertexRepresentitive;
995         const int * pVerts = &piTriListIn[3*iMyTriIndex+0];
996         int i=-1;
997         if (pVerts[0]==iVertRep) i=0;
998         else if (pVerts[1]==iVertRep) i=1;
999         else if (pVerts[2]==iVertRep) i=2;
1000         assert(i>=0 && i<3);
1001
1002         // early out
1003         if (pMyTriInfo->AssignedGroup[i] == pGroup) return TTRUE;
1004         else if (pMyTriInfo->AssignedGroup[i]!=NULL) return TFALSE;
1005         if ((pMyTriInfo->iFlag&GROUP_WITH_ANY)!=0)
1006         {
1007                 // first to group with a group-with-anything triangle
1008                 // determines it's orientation.
1009                 // This is the only existing order dependency in the code!!
1010                 if ( pMyTriInfo->AssignedGroup[0] == NULL &&
1011                         pMyTriInfo->AssignedGroup[1] == NULL &&
1012                         pMyTriInfo->AssignedGroup[2] == NULL )
1013                 {
1014                         pMyTriInfo->iFlag &= (~ORIENT_PRESERVING);
1015                         pMyTriInfo->iFlag |= (pGroup->bOrientPreservering ? ORIENT_PRESERVING : 0);
1016                 }
1017         }
1018         {
1019                 const tbool bOrient = (pMyTriInfo->iFlag&ORIENT_PRESERVING)!=0 ? TTRUE : TFALSE;
1020                 if (bOrient != pGroup->bOrientPreservering) return TFALSE;
1021         }
1022
1023         AddTriToGroup(pGroup, iMyTriIndex);
1024         pMyTriInfo->AssignedGroup[i] = pGroup;
1025
1026         {
1027                 const int neigh_indexL = pMyTriInfo->FaceNeighbors[i];
1028                 const int neigh_indexR = pMyTriInfo->FaceNeighbors[i>0?(i-1):2];
1029                 if (neigh_indexL>=0)
1030                         AssignRecur(piTriListIn, psTriInfos, neigh_indexL, pGroup);
1031                 if (neigh_indexR>=0)
1032                         AssignRecur(piTriListIn, psTriInfos, neigh_indexR, pGroup);
1033         }
1034
1035
1036
1037         return TTRUE;
1038 }
1039
1040 /////////////////////////////////////////////////////////////////////////////////////////////////////
1041 /////////////////////////////////////////////////////////////////////////////////////////////////////
1042
1043 static tbool CompareSubGroups(const SSubGroup * pg1, const SSubGroup * pg2);
1044 static void QuickSort(int* pSortBuffer, int iLeft, int iRight, unsigned int uSeed);
1045 static STSpace EvalTspace(int face_indices[], const int iFaces, const int piTriListIn[], const STriInfo pTriInfos[], const SMikkTSpaceContext * pContext, const int iVertexRepresentitive);
1046
1047 static tbool GenerateTSpaces(STSpace psTspace[], const STriInfo pTriInfos[], const SGroup pGroups[],
1048                              const int iNrActiveGroups, const int piTriListIn[], const float fThresCos,
1049                              const SMikkTSpaceContext * pContext)
1050 {
1051         STSpace * pSubGroupTspace = NULL;
1052         SSubGroup * pUniSubGroups = NULL;
1053         int * pTmpMembers = NULL;
1054         int iMaxNrFaces=0, iUniqueTspaces=0, g=0, i=0;
1055         for (g=0; g<iNrActiveGroups; g++)
1056                 if (iMaxNrFaces < pGroups[g].iNrFaces)
1057                         iMaxNrFaces = pGroups[g].iNrFaces;
1058
1059         if (iMaxNrFaces == 0) return TTRUE;
1060
1061         // make initial allocations
1062         pSubGroupTspace = (STSpace *) malloc(sizeof(STSpace)*iMaxNrFaces);
1063         pUniSubGroups = (SSubGroup *) malloc(sizeof(SSubGroup)*iMaxNrFaces);
1064         pTmpMembers = (int *) malloc(sizeof(int)*iMaxNrFaces);
1065         if (pSubGroupTspace==NULL || pUniSubGroups==NULL || pTmpMembers==NULL)
1066         {
1067                 if (pSubGroupTspace!=NULL) free(pSubGroupTspace);
1068                 if (pUniSubGroups!=NULL) free(pUniSubGroups);
1069                 if (pTmpMembers!=NULL) free(pTmpMembers);
1070                 return TFALSE;
1071         }
1072
1073
1074         iUniqueTspaces = 0;
1075         for (g=0; g<iNrActiveGroups; g++)
1076         {
1077                 const SGroup * pGroup = &pGroups[g];
1078                 int iUniqueSubGroups = 0, s=0;
1079
1080                 for (i=0; i<pGroup->iNrFaces; i++)      // triangles
1081                 {
1082                         const int f = pGroup->pFaceIndices[i];  // triangle number
1083                         int index=-1, iVertIndex=-1, iOF_1=-1, iMembers=0, j=0, l=0;
1084                         SSubGroup tmp_group;
1085                         tbool bFound;
1086                         SVec3 n, vOs, vOt;
1087                         if (pTriInfos[f].AssignedGroup[0]==pGroup) index=0;
1088                         else if (pTriInfos[f].AssignedGroup[1]==pGroup) index=1;
1089                         else if (pTriInfos[f].AssignedGroup[2]==pGroup) index=2;
1090                         assert(index>=0 && index<3);
1091
1092                         iVertIndex = piTriListIn[f*3+index];
1093                         assert(iVertIndex==pGroup->iVertexRepresentitive);
1094
1095                         // is normalized already
1096                         n = GetNormal(pContext, iVertIndex);
1097                         
1098                         // project
1099                         vOs = NormalizeSafe(vsub(pTriInfos[f].vOs, vscale(vdot(n,pTriInfos[f].vOs), n)));
1100                         vOt = NormalizeSafe(vsub(pTriInfos[f].vOt, vscale(vdot(n,pTriInfos[f].vOt), n)));
1101
1102                         // original face number
1103                         iOF_1 = pTriInfos[f].iOrgFaceNumber;
1104                         
1105                         iMembers = 0;
1106                         for (j=0; j<pGroup->iNrFaces; j++)
1107                         {
1108                                 const int t = pGroup->pFaceIndices[j];  // triangle number
1109                                 const int iOF_2 = pTriInfos[t].iOrgFaceNumber;
1110
1111                                 // project
1112                                 SVec3 vOs2 = NormalizeSafe(vsub(pTriInfos[t].vOs, vscale(vdot(n,pTriInfos[t].vOs), n)));
1113                                 SVec3 vOt2 = NormalizeSafe(vsub(pTriInfos[t].vOt, vscale(vdot(n,pTriInfos[t].vOt), n)));
1114
1115                                 {
1116                                         const tbool bAny = ( (pTriInfos[f].iFlag | pTriInfos[t].iFlag) & GROUP_WITH_ANY )!=0 ? TTRUE : TFALSE;
1117                                         // make sure triangles which belong to the same quad are joined.
1118                                         const tbool bSameOrgFace = iOF_1==iOF_2 ? TTRUE : TFALSE;
1119
1120                                         const float fCosS = vdot(vOs,vOs2);
1121                                         const float fCosT = vdot(vOt,vOt2);
1122
1123                                         assert(f!=t || bSameOrgFace);   // sanity check
1124                                         if (bAny || bSameOrgFace || (fCosS>fThresCos && fCosT>fThresCos))
1125                                                 pTmpMembers[iMembers++] = t;
1126                                 }
1127                         }
1128
1129                         // sort pTmpMembers
1130                         tmp_group.iNrFaces = iMembers;
1131                         tmp_group.pTriMembers = pTmpMembers;
1132                         if (iMembers>1)
1133                         {
1134                                 unsigned int uSeed = INTERNAL_RND_SORT_SEED;    // could replace with a random seed?
1135                                 QuickSort(pTmpMembers, 0, iMembers-1, uSeed);
1136                         }
1137
1138                         // look for an existing match
1139                         bFound = TFALSE;
1140                         l=0;
1141                         while (l<iUniqueSubGroups && !bFound)
1142                         {
1143                                 bFound = CompareSubGroups(&tmp_group, &pUniSubGroups[l]);
1144                                 if (!bFound) ++l;
1145                         }
1146                         
1147                         // assign tangent space index
1148                         assert(bFound || l==iUniqueSubGroups);
1149                         //piTempTangIndices[f*3+index] = iUniqueTspaces+l;
1150
1151                         // if no match was found we allocate a new subgroup
1152                         if (!bFound)
1153                         {
1154                                 // insert new subgroup
1155                                 int * pIndices = (int *) malloc(sizeof(int)*iMembers);
1156                                 if (pIndices==NULL)
1157                                 {
1158                                         // clean up and return false
1159                                         int s=0;
1160                                         for (s=0; s<iUniqueSubGroups; s++)
1161                                                 free(pUniSubGroups[s].pTriMembers);
1162                                         free(pUniSubGroups);
1163                                         free(pTmpMembers);
1164                                         free(pSubGroupTspace);
1165                                         return TFALSE;
1166                                 }
1167                                 pUniSubGroups[iUniqueSubGroups].iNrFaces = iMembers;
1168                                 pUniSubGroups[iUniqueSubGroups].pTriMembers = pIndices;
1169                                 memcpy(pIndices, tmp_group.pTriMembers, sizeof(int)*iMembers);
1170                                 pSubGroupTspace[iUniqueSubGroups] =
1171                                         EvalTspace(tmp_group.pTriMembers, iMembers, piTriListIn, pTriInfos, pContext, pGroup->iVertexRepresentitive);
1172                                 ++iUniqueSubGroups;
1173                         }
1174
1175                         // output tspace
1176                         {
1177                                 const int iOffs = pTriInfos[f].iTSpacesOffs;
1178                                 const int iVert = pTriInfos[f].vert_num[index];
1179                                 STSpace * pTS_out = &psTspace[iOffs+iVert];
1180                                 assert(pTS_out->iCounter<2);
1181                                 assert(((pTriInfos[f].iFlag&ORIENT_PRESERVING)!=0) == pGroup->bOrientPreservering);
1182                                 if (pTS_out->iCounter==1)
1183                                 {
1184                                         *pTS_out = AvgTSpace(pTS_out, &pSubGroupTspace[l]);
1185                                         pTS_out->iCounter = 2;  // update counter
1186                                         pTS_out->bOrient = pGroup->bOrientPreservering;
1187                                 }
1188                                 else
1189                                 {
1190                                         assert(pTS_out->iCounter==0);
1191                                         *pTS_out = pSubGroupTspace[l];
1192                                         pTS_out->iCounter = 1;  // update counter
1193                                         pTS_out->bOrient = pGroup->bOrientPreservering;
1194                                 }
1195                         }
1196                 }
1197
1198                 // clean up and offset iUniqueTspaces
1199                 for (s=0; s<iUniqueSubGroups; s++)
1200                         free(pUniSubGroups[s].pTriMembers);
1201                 iUniqueTspaces += iUniqueSubGroups;
1202         }
1203
1204         // clean up
1205         free(pUniSubGroups);
1206         free(pTmpMembers);
1207         free(pSubGroupTspace);
1208
1209         return TTRUE;
1210 }
1211
1212 static STSpace EvalTspace(int face_indices[], const int iFaces, const int piTriListIn[], const STriInfo pTriInfos[],
1213                           const SMikkTSpaceContext * pContext, const int iVertexRepresentitive)
1214 {
1215         STSpace res;
1216         float fAngleSum = 0;
1217         int face=0;
1218         res.vOs.x=0.0f; res.vOs.y=0.0f; res.vOs.z=0.0f;
1219         res.vOt.x=0.0f; res.vOt.y=0.0f; res.vOt.z=0.0f;
1220         res.fMagS = 0; res.fMagT = 0;
1221
1222         for (face=0; face<iFaces; face++)
1223         {
1224                 const int f = face_indices[face];
1225
1226                 // only valid triangles get to add their contribution
1227                 if ( (pTriInfos[f].iFlag&GROUP_WITH_ANY)==0 )
1228                 {
1229                         SVec3 n, vOs, vOt, p0, p1, p2, v1, v2;
1230                         float fCos, fAngle, fMagS, fMagT;
1231                         int i=-1, index=-1, i0=-1, i1=-1, i2=-1;
1232                         if (piTriListIn[3*f+0]==iVertexRepresentitive) i=0;
1233                         else if (piTriListIn[3*f+1]==iVertexRepresentitive) i=1;
1234                         else if (piTriListIn[3*f+2]==iVertexRepresentitive) i=2;
1235                         assert(i>=0 && i<3);
1236
1237                         // project
1238                         index = piTriListIn[3*f+i];
1239                         n = GetNormal(pContext, index);
1240                         vOs = NormalizeSafe(vsub(pTriInfos[f].vOs, vscale(vdot(n,pTriInfos[f].vOs), n)));
1241                         vOt = NormalizeSafe(vsub(pTriInfos[f].vOt, vscale(vdot(n,pTriInfos[f].vOt), n)));
1242
1243                         i2 = piTriListIn[3*f + (i<2?(i+1):0)];
1244                         i1 = piTriListIn[3*f + i];
1245                         i0 = piTriListIn[3*f + (i>0?(i-1):2)];
1246
1247                         p0 = GetPosition(pContext, i0);
1248                         p1 = GetPosition(pContext, i1);
1249                         p2 = GetPosition(pContext, i2);
1250                         v1 = vsub(p0,p1);
1251                         v2 = vsub(p2,p1);
1252
1253                         // project
1254                         v1 = NormalizeSafe(vsub(v1, vscale(vdot(n,v1),n)));
1255                         v2 = NormalizeSafe(vsub(v2, vscale(vdot(n,v2),n)));
1256
1257                         // weight contribution by the angle
1258                         // between the two edge vectors
1259                         fCos = vdot(v1,v2); fCos=fCos>1?1:(fCos<(-1) ? (-1) : fCos);
1260                         fAngle = (float) acos(fCos);
1261                         fMagS = pTriInfos[f].fMagS;
1262                         fMagT = pTriInfos[f].fMagT;
1263
1264                         res.vOs=vadd(res.vOs, vscale(fAngle,vOs));
1265                         res.vOt=vadd(res.vOt,vscale(fAngle,vOt));
1266                         res.fMagS+=(fAngle*fMagS);
1267                         res.fMagT+=(fAngle*fMagT);
1268                         fAngleSum += fAngle;
1269                 }
1270         }
1271
1272         // normalize
1273         res.vOs = NormalizeSafe(res.vOs);
1274         res.vOt = NormalizeSafe(res.vOt);
1275         if (fAngleSum>0)
1276         {
1277                 res.fMagS /= fAngleSum;
1278                 res.fMagT /= fAngleSum;
1279         }
1280
1281         return res;
1282 }
1283
1284 static tbool CompareSubGroups(const SSubGroup * pg1, const SSubGroup * pg2)
1285 {
1286         tbool bStillSame=TTRUE;
1287         int i=0;
1288         if (pg1->iNrFaces!=pg2->iNrFaces) return TFALSE;
1289         while (i<pg1->iNrFaces && bStillSame)
1290         {
1291                 bStillSame = pg1->pTriMembers[i]==pg2->pTriMembers[i] ? TTRUE : TFALSE;
1292                 if (bStillSame) ++i;
1293         }
1294         return bStillSame;
1295 }
1296
1297 static void QuickSort(int* pSortBuffer, int iLeft, int iRight, unsigned int uSeed)
1298 {
1299         int iL, iR, n, index, iMid, iTmp;
1300
1301         // Random
1302         unsigned int t=uSeed&31;
1303         t=(uSeed<<t)|(uSeed>>(32-t));
1304         uSeed=uSeed+t+3;
1305         // Random end
1306
1307         iL=iLeft; iR=iRight;
1308         n = (iR-iL)+1;
1309         assert(n>=0);
1310         index = (int) (uSeed%(unsigned int)n);
1311
1312         iMid=pSortBuffer[index + iL];
1313
1314
1315         do
1316         {
1317                 while (pSortBuffer[iL] < iMid)
1318                         ++iL;
1319                 while (pSortBuffer[iR] > iMid)
1320                         --iR;
1321
1322                 if (iL <= iR)
1323                 {
1324                         iTmp = pSortBuffer[iL];
1325                         pSortBuffer[iL] = pSortBuffer[iR];
1326                         pSortBuffer[iR] = iTmp;
1327                         ++iL; --iR;
1328                 }
1329         }
1330         while (iL <= iR);
1331
1332         if (iLeft < iR)
1333                 QuickSort(pSortBuffer, iLeft, iR, uSeed);
1334         if (iL < iRight)
1335                 QuickSort(pSortBuffer, iL, iRight, uSeed);
1336 }
1337
1338 /////////////////////////////////////////////////////////////////////////////////////////////
1339 /////////////////////////////////////////////////////////////////////////////////////////////
1340
1341 static void QuickSortEdges(SEdge * pSortBuffer, int iLeft, int iRight, const int channel, unsigned int uSeed);
1342 static void GetEdge(int * i0_out, int * i1_out, int * edgenum_out, const int indices[], const int i0_in, const int i1_in);
1343
1344 static void BuildNeighborsFast(STriInfo pTriInfos[], SEdge * pEdges, const int piTriListIn[], const int iNrTrianglesIn)
1345 {
1346         // build array of edges
1347         unsigned int uSeed = INTERNAL_RND_SORT_SEED;                            // could replace with a random seed?
1348         int iEntries=0, iCurStartIndex=-1, f=0, i=0;
1349         for (f=0; f<iNrTrianglesIn; f++)
1350                 for (i=0; i<3; i++)
1351                 {
1352                         const int i0 = piTriListIn[f*3+i];
1353                         const int i1 = piTriListIn[f*3+(i<2?(i+1):0)];
1354                         pEdges[f*3+i].i0 = i0 < i1 ? i0 : i1;                   // put minimum index in i0
1355                         pEdges[f*3+i].i1 = !(i0 < i1) ? i0 : i1;                // put maximum index in i1
1356                         pEdges[f*3+i].f = f;                                                    // record face number
1357                 }
1358
1359         // sort over all edges by i0, this is the pricy one.
1360         QuickSortEdges(pEdges, 0, iNrTrianglesIn*3-1, 0, uSeed);        // sort channel 0 which is i0
1361
1362         // sub sort over i1, should be fast.
1363         // could replace this with a 64 bit int sort over (i0,i1)
1364         // with i0 as msb in the quicksort call above.
1365         iEntries = iNrTrianglesIn*3;
1366         iCurStartIndex = 0;
1367         for (i=1; i<iEntries; i++)
1368         {
1369                 if (pEdges[iCurStartIndex].i0 != pEdges[i].i0)
1370                 {
1371                         const int iL = iCurStartIndex;
1372                         const int iR = i-1;
1373                         //const int iElems = i-iL;
1374                         iCurStartIndex = i;
1375                         QuickSortEdges(pEdges, iL, iR, 1, uSeed);       // sort channel 1 which is i1
1376                 }
1377         }
1378
1379         // sub sort over f, which should be fast.
1380         // this step is to remain compliant with BuildNeighborsSlow() when
1381         // more than 2 triangles use the same edge (such as a butterfly topology).
1382         iCurStartIndex = 0;
1383         for (i=1; i<iEntries; i++)
1384         {
1385                 if (pEdges[iCurStartIndex].i0 != pEdges[i].i0 || pEdges[iCurStartIndex].i1 != pEdges[i].i1)
1386                 {
1387                         const int iL = iCurStartIndex;
1388                         const int iR = i-1;
1389                         //const int iElems = i-iL;
1390                         iCurStartIndex = i;
1391                         QuickSortEdges(pEdges, iL, iR, 2, uSeed);       // sort channel 2 which is f
1392                 }
1393         }
1394
1395         // pair up, adjacent triangles
1396         for (i=0; i<iEntries; i++)
1397         {
1398                 const int i0=pEdges[i].i0;
1399                 const int i1=pEdges[i].i1;
1400                 const int f = pEdges[i].f;
1401                 tbool bUnassigned_A;
1402
1403                 int i0_A, i1_A;
1404                 int edgenum_A, edgenum_B=0;     // 0,1 or 2
1405                 GetEdge(&i0_A, &i1_A, &edgenum_A, &piTriListIn[f*3], i0, i1);   // resolve index ordering and edge_num
1406                 bUnassigned_A = pTriInfos[f].FaceNeighbors[edgenum_A] == -1 ? TTRUE : TFALSE;
1407
1408                 if (bUnassigned_A)
1409                 {
1410                         // get true index ordering
1411                         int j=i+1, t;
1412                         tbool bNotFound = TTRUE;
1413                         while (j<iEntries && i0==pEdges[j].i0 && i1==pEdges[j].i1 && bNotFound)
1414                         {
1415                                 tbool bUnassigned_B;
1416                                 int i0_B, i1_B;
1417                                 t = pEdges[j].f;
1418                                 // flip i0_B and i1_B
1419                                 GetEdge(&i1_B, &i0_B, &edgenum_B, &piTriListIn[t*3], pEdges[j].i0, pEdges[j].i1);       // resolve index ordering and edge_num
1420                                 //assert(!(i0_A==i1_B && i1_A==i0_B));
1421                                 bUnassigned_B =  pTriInfos[t].FaceNeighbors[edgenum_B]==-1 ? TTRUE : TFALSE;
1422                                 if (i0_A==i0_B && i1_A==i1_B && bUnassigned_B)
1423                                         bNotFound = TFALSE;
1424                                 else
1425                                         ++j;
1426                         }
1427
1428                         if (!bNotFound)
1429                         {
1430                                 int t = pEdges[j].f;
1431                                 pTriInfos[f].FaceNeighbors[edgenum_A] = t;
1432                                 //assert(pTriInfos[t].FaceNeighbors[edgenum_B]==-1);
1433                                 pTriInfos[t].FaceNeighbors[edgenum_B] = f;
1434                         }
1435                 }
1436         }
1437 }
1438
1439 static void BuildNeighborsSlow(STriInfo pTriInfos[], const int piTriListIn[], const int iNrTrianglesIn)
1440 {
1441         int f=0, i=0;
1442         for (f=0; f<iNrTrianglesIn; f++)
1443         {
1444                 for (i=0; i<3; i++)
1445                 {
1446                         // if unassigned
1447                         if (pTriInfos[f].FaceNeighbors[i] == -1)
1448                         {
1449                                 const int i0_A = piTriListIn[f*3+i];
1450                                 const int i1_A = piTriListIn[f*3+(i<2?(i+1):0)];
1451
1452                                 // search for a neighbor
1453                                 tbool bFound = TFALSE;
1454                                 int t=0, j=0;
1455                                 while (!bFound && t<iNrTrianglesIn)
1456                                 {
1457                                         if (t!=f)
1458                                         {
1459                                                 j=0;
1460                                                 while (!bFound && j<3)
1461                                                 {
1462                                                         // in rev order
1463                                                         const int i1_B = piTriListIn[t*3+j];
1464                                                         const int i0_B = piTriListIn[t*3+(j<2?(j+1):0)];
1465                                                         //assert(!(i0_A==i1_B && i1_A==i0_B));
1466                                                         if (i0_A==i0_B && i1_A==i1_B)
1467                                                                 bFound = TTRUE;
1468                                                         else
1469                                                                 ++j;
1470                                                 }
1471                                         }
1472                                         
1473                                         if (!bFound) ++t;
1474                                 }
1475
1476                                 // assign neighbors
1477                                 if (bFound)
1478                                 {
1479                                         pTriInfos[f].FaceNeighbors[i] = t;
1480                                         //assert(pTriInfos[t].FaceNeighbors[j]==-1);
1481                                         pTriInfos[t].FaceNeighbors[j] = f;
1482                                 }
1483                         }
1484                 }
1485         }
1486 }
1487
1488 static void QuickSortEdges(SEdge * pSortBuffer, int iLeft, int iRight, const int channel, unsigned int uSeed)
1489 {
1490         unsigned int t;
1491         int iL, iR, n, index, iMid;
1492
1493         // early out
1494         SEdge sTmp;
1495         const int iElems = iRight-iLeft+1;
1496         if (iElems<2) return;
1497         else if (iElems==2)
1498         {
1499                 if (pSortBuffer[iLeft].array[channel] > pSortBuffer[iRight].array[channel])
1500                 {
1501                         sTmp = pSortBuffer[iLeft];
1502                         pSortBuffer[iLeft] = pSortBuffer[iRight];
1503                         pSortBuffer[iRight] = sTmp;
1504                 }
1505                 return;
1506         }
1507         else if(iElems < 16) {
1508                 int i, j;
1509                 for (i = 0; i < iElems - 1; i++) {
1510                         for (j = 0; j < iElems - i - 1; j++) {
1511                                 int index = iLeft + j;
1512                                 if (pSortBuffer[index].array[channel] > pSortBuffer[index + 1].array[channel]) {
1513                                         sTmp = pSortBuffer[index];
1514                                         pSortBuffer[index] = pSortBuffer[index + 1];
1515                                         pSortBuffer[index + 1] = sTmp;
1516                                 }
1517                         }
1518                 }
1519                 return;
1520         }
1521
1522         // Random
1523         t=uSeed&31;
1524         t=(uSeed<<t)|(uSeed>>(32-t));
1525         uSeed=uSeed+t+3;
1526         // Random end
1527
1528         iL = iLeft;
1529         iR = iRight;
1530         n = (iR-iL)+1;
1531         assert(n>=0);
1532         index = (int) (uSeed%(unsigned int)n);
1533
1534         iMid=pSortBuffer[index + iL].array[channel];
1535
1536         do
1537         {
1538                 while (pSortBuffer[iL].array[channel] < iMid)
1539                         ++iL;
1540                 while (pSortBuffer[iR].array[channel] > iMid)
1541                         --iR;
1542
1543                 if (iL <= iR)
1544                 {
1545                         sTmp = pSortBuffer[iL];
1546                         pSortBuffer[iL] = pSortBuffer[iR];
1547                         pSortBuffer[iR] = sTmp;
1548                         ++iL; --iR;
1549                 }
1550         }
1551         while (iL <= iR);
1552
1553         if (iLeft < iR)
1554                 QuickSortEdges(pSortBuffer, iLeft, iR, channel, uSeed);
1555         if (iL < iRight)
1556                 QuickSortEdges(pSortBuffer, iL, iRight, channel, uSeed);
1557 }
1558
1559 // resolve ordering and edge number
1560 static void GetEdge(int * i0_out, int * i1_out, int * edgenum_out, const int indices[], const int i0_in, const int i1_in)
1561 {
1562         *edgenum_out = -1;
1563         
1564         // test if first index is on the edge
1565         if (indices[0]==i0_in || indices[0]==i1_in)
1566         {
1567                 // test if second index is on the edge
1568                 if (indices[1]==i0_in || indices[1]==i1_in)
1569                 {
1570                         edgenum_out[0]=0;       // first edge
1571                         i0_out[0]=indices[0];
1572                         i1_out[0]=indices[1];
1573                 }
1574                 else
1575                 {
1576                         edgenum_out[0]=2;       // third edge
1577                         i0_out[0]=indices[2];
1578                         i1_out[0]=indices[0];
1579                 }
1580         }
1581         else
1582         {
1583                 // only second and third index is on the edge
1584                 edgenum_out[0]=1;       // second edge
1585                 i0_out[0]=indices[1];
1586                 i1_out[0]=indices[2];
1587         }
1588 }
1589
1590
1591 /////////////////////////////////////////////////////////////////////////////////////////////
1592 /////////////////////////////////// Degenerate triangles ////////////////////////////////////
1593
1594 static void DegenPrologue(STriInfo pTriInfos[], int piTriList_out[], const int iNrTrianglesIn, const int iTotTris)
1595 {
1596         int iNextGoodTriangleSearchIndex=-1;
1597         tbool bStillFindingGoodOnes;
1598
1599         // locate quads with only one good triangle
1600         int t=0;
1601         while (t<(iTotTris-1))
1602         {
1603                 const int iFO_a = pTriInfos[t].iOrgFaceNumber;
1604                 const int iFO_b = pTriInfos[t+1].iOrgFaceNumber;
1605                 if (iFO_a==iFO_b)       // this is a quad
1606                 {
1607                         const tbool bIsDeg_a = (pTriInfos[t].iFlag&MARK_DEGENERATE)!=0 ? TTRUE : TFALSE;
1608                         const tbool bIsDeg_b = (pTriInfos[t+1].iFlag&MARK_DEGENERATE)!=0 ? TTRUE : TFALSE;
1609                         if ((bIsDeg_a^bIsDeg_b)!=0)
1610                         {
1611                                 pTriInfos[t].iFlag |= QUAD_ONE_DEGEN_TRI;
1612                                 pTriInfos[t+1].iFlag |= QUAD_ONE_DEGEN_TRI;
1613                         }
1614                         t += 2;
1615                 }
1616                 else
1617                         ++t;
1618         }
1619
1620         // reorder list so all degen triangles are moved to the back
1621         // without reordering the good triangles
1622         iNextGoodTriangleSearchIndex = 1;
1623         t=0;
1624         bStillFindingGoodOnes = TTRUE;
1625         while (t<iNrTrianglesIn && bStillFindingGoodOnes)
1626         {
1627                 const tbool bIsGood = (pTriInfos[t].iFlag&MARK_DEGENERATE)==0 ? TTRUE : TFALSE;
1628                 if (bIsGood)
1629                 {
1630                         if (iNextGoodTriangleSearchIndex < (t+2))
1631                                 iNextGoodTriangleSearchIndex = t+2;
1632                 }
1633                 else
1634                 {
1635                         int t0, t1;
1636                         // search for the first good triangle.
1637                         tbool bJustADegenerate = TTRUE;
1638                         while (bJustADegenerate && iNextGoodTriangleSearchIndex<iTotTris)
1639                         {
1640                                 const tbool bIsGood = (pTriInfos[iNextGoodTriangleSearchIndex].iFlag&MARK_DEGENERATE)==0 ? TTRUE : TFALSE;
1641                                 if (bIsGood) bJustADegenerate=TFALSE;
1642                                 else ++iNextGoodTriangleSearchIndex;
1643                         }
1644
1645                         t0 = t;
1646                         t1 = iNextGoodTriangleSearchIndex;
1647                         ++iNextGoodTriangleSearchIndex;
1648                         assert(iNextGoodTriangleSearchIndex > (t+1));
1649
1650                         // swap triangle t0 and t1
1651                         if (!bJustADegenerate)
1652                         {
1653                                 int i=0;
1654                                 for (i=0; i<3; i++)
1655                                 {
1656                                         const int index = piTriList_out[t0*3+i];
1657                                         piTriList_out[t0*3+i] = piTriList_out[t1*3+i];
1658                                         piTriList_out[t1*3+i] = index;
1659                                 }
1660                                 {
1661                                         const STriInfo tri_info = pTriInfos[t0];
1662                                         pTriInfos[t0] = pTriInfos[t1];
1663                                         pTriInfos[t1] = tri_info;
1664                                 }
1665                         }
1666                         else
1667                                 bStillFindingGoodOnes = TFALSE; // this is not supposed to happen
1668                 }
1669
1670                 if (bStillFindingGoodOnes) ++t;
1671         }
1672
1673         assert(bStillFindingGoodOnes);  // code will still work.
1674         assert(iNrTrianglesIn == t);
1675 }
1676
1677 typedef struct VertReverseLookupContext {
1678         tbool bIsInitialized;
1679         int * pLookup;
1680         int iMaxVertIndex;
1681 } VertReverseLookupContext;
1682
1683 static void GenerateReverseLookup(
1684         const int piTriListIn[],
1685         const int iNrTrianglesIn,
1686         VertReverseLookupContext *pLookupCtx)
1687 {
1688         int t;
1689         // Figure out what size of lookup array we need.
1690         pLookupCtx->iMaxVertIndex = -1;
1691         for (t=0; t<3*iNrTrianglesIn; t++)
1692         {
1693                 int iVertIndex = piTriListIn[t];
1694                 if (iVertIndex > pLookupCtx->iMaxVertIndex) {
1695                         pLookupCtx->iMaxVertIndex = iVertIndex;
1696                 }
1697         }
1698         // Allocate memory.
1699         if (pLookupCtx->iMaxVertIndex < 1)
1700         {
1701                 // Nothing to allocate, all triangles are degenerate.
1702                 return;
1703         }
1704         pLookupCtx->pLookup = malloc(sizeof(int) * (pLookupCtx->iMaxVertIndex + 1));
1705         if (pLookupCtx->pLookup == NULL)
1706         {
1707                 // Most likely run out of memory.
1708                 return;
1709         }
1710         // Fill in lookup.
1711         for (t=0; t<=pLookupCtx->iMaxVertIndex; t++) {
1712                 pLookupCtx->pLookup[t] = -1;
1713         }
1714         for (t=0; t<3*iNrTrianglesIn; t++)
1715         {
1716                 int iVertIndex = piTriListIn[t];
1717                 if (pLookupCtx->pLookup[iVertIndex] != -1)
1718                 {
1719                         continue;
1720                 }
1721                 pLookupCtx->pLookup[iVertIndex] = t;
1722         }
1723 }
1724
1725 static int LookupVertexIndexFromGoodTriangle(
1726         VertReverseLookupContext *pLookupCtx,
1727         int piTriListIn[],
1728         const int iNrTrianglesIn,
1729         const int iVertexIndex)
1730 {
1731         // Allocate lookup on demand.
1732         if (!pLookupCtx->bIsInitialized)
1733         {
1734                 GenerateReverseLookup(piTriListIn,
1735                                       iNrTrianglesIn,
1736                                       pLookupCtx);
1737                 pLookupCtx->bIsInitialized = TTRUE;
1738         }
1739         // Make sure vertex index is in the mapping.
1740         if (iVertexIndex > pLookupCtx->iMaxVertIndex)
1741         {
1742                 return -1;
1743         }
1744         if (pLookupCtx->pLookup == NULL) {
1745                 return -1;
1746         }
1747         // Perform actual lookup.
1748         return pLookupCtx->pLookup[iVertexIndex];
1749 }
1750
1751 static void FreeReverseLookup(VertReverseLookupContext *pLookupCtx)
1752 {
1753         if (!pLookupCtx->bIsInitialized) {
1754                 return;
1755         }
1756         if (pLookupCtx->pLookup != NULL) {
1757                 free(pLookupCtx->pLookup);
1758         }
1759 }
1760
1761 static void DegenEpilogue(STSpace psTspace[],
1762                           STriInfo pTriInfos[],
1763                           int piTriListIn[],
1764                           const SMikkTSpaceContext * pContext,
1765                           const int iNrTrianglesIn,
1766                           const int iTotTris)
1767 {
1768         int t=0, i=0;
1769         VertReverseLookupContext lookupCtx = { TFALSE };
1770         // deal with degenerate triangles
1771         // punishment for degenerate triangles is O(iNrTrianglesIn) extra memory.
1772         for (t=iNrTrianglesIn; t<iTotTris; t++)
1773         {
1774                 // degenerate triangles on a quad with one good triangle are skipped
1775                 // here but processed in the next loop
1776                 const tbool bSkip = (pTriInfos[t].iFlag&QUAD_ONE_DEGEN_TRI)!=0 ? TTRUE : TFALSE;
1777                 if (bSkip) {
1778                         continue;
1779                 }
1780
1781                 for (i=0; i<3; i++)
1782                 {
1783                         const int index1 = piTriListIn[t*3+i];
1784                         int j = LookupVertexIndexFromGoodTriangle(&lookupCtx,
1785                                                                   piTriListIn,
1786                                                                   iNrTrianglesIn,
1787                                                                   index1);
1788                         if (j < 0)
1789                         {
1790                                 // Matching vertex from good triangle is not found.
1791                                 continue;
1792                         }
1793
1794                         const int iTri = j/3;
1795                         const int iVert = j%3;
1796                         const int iSrcVert=pTriInfos[iTri].vert_num[iVert];
1797                         const int iSrcOffs=pTriInfos[iTri].iTSpacesOffs;
1798                         const int iDstVert=pTriInfos[t].vert_num[i];
1799                         const int iDstOffs=pTriInfos[t].iTSpacesOffs;
1800                         // copy tspace
1801                         psTspace[iDstOffs+iDstVert] = psTspace[iSrcOffs+iSrcVert];
1802                 }
1803         }
1804         FreeReverseLookup(&lookupCtx);
1805
1806         // deal with degenerate quads with one good triangle
1807         for (t=0; t<iNrTrianglesIn; t++)
1808         {
1809                 // this triangle belongs to a quad where the
1810                 // other triangle is degenerate
1811                 if ( (pTriInfos[t].iFlag&QUAD_ONE_DEGEN_TRI)!=0 )
1812                 {
1813                         SVec3 vDstP;
1814                         int iOrgF=-1, i=0;
1815                         tbool bNotFound;
1816                         unsigned char * pV = pTriInfos[t].vert_num;
1817                         int iFlag = (1<<pV[0]) | (1<<pV[1]) | (1<<pV[2]);
1818                         int iMissingIndex = 0;
1819                         if ((iFlag&2)==0) iMissingIndex=1;
1820                         else if ((iFlag&4)==0) iMissingIndex=2;
1821                         else if ((iFlag&8)==0) iMissingIndex=3;
1822
1823                         iOrgF = pTriInfos[t].iOrgFaceNumber;
1824                         vDstP = GetPosition(pContext, MakeIndex(iOrgF, iMissingIndex));
1825                         bNotFound = TTRUE;
1826                         i=0;
1827                         while (bNotFound && i<3)
1828                         {
1829                                 const int iVert = pV[i];
1830                                 const SVec3 vSrcP = GetPosition(pContext, MakeIndex(iOrgF, iVert));
1831                                 if (veq(vSrcP, vDstP)==TTRUE)
1832                                 {
1833                                         const int iOffs = pTriInfos[t].iTSpacesOffs;
1834                                         psTspace[iOffs+iMissingIndex] = psTspace[iOffs+iVert];
1835                                         bNotFound=TFALSE;
1836                                 }
1837                                 else
1838                                         ++i;
1839                         }
1840                         assert(!bNotFound);
1841                 }
1842         }
1843 }