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