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