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