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