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