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