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