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