aboutsummaryrefslogtreecommitdiff
path: root/contrib/cgltf-tangents/MikkTSpace
diff options
context:
space:
mode:
Diffstat (limited to 'contrib/cgltf-tangents/MikkTSpace')
-rw-r--r--contrib/cgltf-tangents/MikkTSpace/README.md4
-rw-r--r--contrib/cgltf-tangents/MikkTSpace/mikktspace.c1899
-rw-r--r--contrib/cgltf-tangents/MikkTSpace/mikktspace.h145
3 files changed, 2048 insertions, 0 deletions
diff --git a/contrib/cgltf-tangents/MikkTSpace/README.md b/contrib/cgltf-tangents/MikkTSpace/README.md
new file mode 100644
index 0000000..9fda155
--- /dev/null
+++ b/contrib/cgltf-tangents/MikkTSpace/README.md
@@ -0,0 +1,4 @@
1# MikkTSpace
2A common standard for tangent space used in baking tools to produce normal maps.
3
4More information can be found at http://www.mikktspace.com/.
diff --git a/contrib/cgltf-tangents/MikkTSpace/mikktspace.c b/contrib/cgltf-tangents/MikkTSpace/mikktspace.c
new file mode 100644
index 0000000..0342ae0
--- /dev/null
+++ b/contrib/cgltf-tangents/MikkTSpace/mikktspace.c
@@ -0,0 +1,1899 @@
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;
481 fMax = vMax.y;
482 }
483 else if (vDim.z>vDim.x)
484 {
485 iChannel=2;
486 fMin = vMin.z;
487 fMax = vMax.z;
488 }
489
490 // make allocations
491 piHashTable = (int *) malloc(sizeof(int)*iNrTrianglesIn*3);
492 piHashCount = (int *) malloc(sizeof(int)*g_iCells);
493 piHashOffsets = (int *) malloc(sizeof(int)*g_iCells);
494 piHashCount2 = (int *) malloc(sizeof(int)*g_iCells);
495
496 if (piHashTable==NULL || piHashCount==NULL || piHashOffsets==NULL || piHashCount2==NULL)
497 {
498 if (piHashTable!=NULL) free(piHashTable);
499 if (piHashCount!=NULL) free(piHashCount);
500 if (piHashOffsets!=NULL) free(piHashOffsets);
501 if (piHashCount2!=NULL) free(piHashCount2);
502 GenerateSharedVerticesIndexListSlow(piTriList_in_and_out, pContext, iNrTrianglesIn);
503 return;
504 }
505 memset(piHashCount, 0, sizeof(int)*g_iCells);
506 memset(piHashCount2, 0, sizeof(int)*g_iCells);
507
508 // count amount of elements in each cell unit
509 for (i=0; i<(iNrTrianglesIn*3); i++)
510 {
511 const int index = piTriList_in_and_out[i];
512 const SVec3 vP = GetPosition(pContext, index);
513 const float fVal = iChannel==0 ? vP.x : (iChannel==1 ? vP.y : vP.z);
514 const int iCell = FindGridCell(fMin, fMax, fVal);
515 ++piHashCount[iCell];
516 }
517
518 // evaluate start index of each cell.
519 piHashOffsets[0]=0;
520 for (k=1; k<g_iCells; k++)
521 piHashOffsets[k]=piHashOffsets[k-1]+piHashCount[k-1];
522
523 // insert vertices
524 for (i=0; i<(iNrTrianglesIn*3); i++)
525 {
526 const int index = piTriList_in_and_out[i];
527 const SVec3 vP = GetPosition(pContext, index);
528 const float fVal = iChannel==0 ? vP.x : (iChannel==1 ? vP.y : vP.z);
529 const int iCell = FindGridCell(fMin, fMax, fVal);
530 int * pTable = NULL;
531
532 assert(piHashCount2[iCell]<piHashCount[iCell]);
533 pTable = &piHashTable[piHashOffsets[iCell]];
534 pTable[piHashCount2[iCell]] = i; // vertex i has been inserted.
535 ++piHashCount2[iCell];
536 }
537 for (k=0; k<g_iCells; k++)
538 assert(piHashCount2[k] == piHashCount[k]); // verify the count
539 free(piHashCount2);
540
541 // find maximum amount of entries in any hash entry
542 iMaxCount = piHashCount[0];
543 for (k=1; k<g_iCells; k++)
544 if (iMaxCount<piHashCount[k])
545 iMaxCount=piHashCount[k];
546 pTmpVert = (STmpVert *) malloc(sizeof(STmpVert)*iMaxCount);
547
548
549 // complete the merge
550 for (k=0; k<g_iCells; k++)
551 {
552 // extract table of cell k and amount of entries in it
553 int * pTable = &piHashTable[piHashOffsets[k]];
554 const int iEntries = piHashCount[k];
555 if (iEntries < 2) continue;
556
557 if (pTmpVert!=NULL)
558 {
559 for (e=0; e<iEntries; e++)
560 {
561 int i = pTable[e];
562 const SVec3 vP = GetPosition(pContext, piTriList_in_and_out[i]);
563 pTmpVert[e].vert[0] = vP.x; pTmpVert[e].vert[1] = vP.y;
564 pTmpVert[e].vert[2] = vP.z; pTmpVert[e].index = i;
565 }
566 MergeVertsFast(piTriList_in_and_out, pTmpVert, pContext, 0, iEntries-1);
567 }
568 else
569 MergeVertsSlow(piTriList_in_and_out, pContext, pTable, iEntries);
570 }
571
572 if (pTmpVert!=NULL) { free(pTmpVert); }
573 free(piHashTable);
574 free(piHashCount);
575 free(piHashOffsets);
576}
577
578static void MergeVertsFast(int piTriList_in_and_out[], STmpVert pTmpVert[], const SMikkTSpaceContext * pContext, const int iL_in, const int iR_in)
579{
580 // make bbox
581 int c=0, l=0, channel=0;
582 float fvMin[3], fvMax[3];
583 float dx=0, dy=0, dz=0, fSep=0;
584 for (c=0; c<3; c++)
585 { fvMin[c]=pTmpVert[iL_in].vert[c]; fvMax[c]=fvMin[c]; }
586 for (l=(iL_in+1); l<=iR_in; l++) {
587 for (c=0; c<3; c++) {
588 if (fvMin[c]>pTmpVert[l].vert[c]) fvMin[c]=pTmpVert[l].vert[c];
589 if (fvMax[c]<pTmpVert[l].vert[c]) fvMax[c]=pTmpVert[l].vert[c];
590 }
591 }
592
593 dx = fvMax[0]-fvMin[0];
594 dy = fvMax[1]-fvMin[1];
595 dz = fvMax[2]-fvMin[2];
596
597 channel = 0;
598 if (dy>dx && dy>dz) channel=1;
599 else if (dz>dx) channel=2;
600
601 fSep = 0.5f*(fvMax[channel]+fvMin[channel]);
602
603 // stop if all vertices are NaNs
604 if (!isfinite(fSep))
605 return;
606
607 // terminate recursion when the separation/average value
608 // is no longer strictly between fMin and fMax values.
609 if (fSep>=fvMax[channel] || fSep<=fvMin[channel])
610 {
611 // complete the weld
612 for (l=iL_in; l<=iR_in; l++)
613 {
614 int i = pTmpVert[l].index;
615 const int index = piTriList_in_and_out[i];
616 const SVec3 vP = GetPosition(pContext, index);
617 const SVec3 vN = GetNormal(pContext, index);
618 const SVec3 vT = GetTexCoord(pContext, index);
619
620 tbool bNotFound = TTRUE;
621 int l2=iL_in, i2rec=-1;
622 while (l2<l && bNotFound)
623 {
624 const int i2 = pTmpVert[l2].index;
625 const int index2 = piTriList_in_and_out[i2];
626 const SVec3 vP2 = GetPosition(pContext, index2);
627 const SVec3 vN2 = GetNormal(pContext, index2);
628 const SVec3 vT2 = GetTexCoord(pContext, index2);
629 i2rec=i2;
630
631 //if (vP==vP2 && vN==vN2 && vT==vT2)
632 if (vP.x==vP2.x && vP.y==vP2.y && vP.z==vP2.z &&
633 vN.x==vN2.x && vN.y==vN2.y && vN.z==vN2.z &&
634 vT.x==vT2.x && vT.y==vT2.y && vT.z==vT2.z)
635 bNotFound = TFALSE;
636 else
637 ++l2;
638 }
639
640 // merge if previously found
641 if (!bNotFound)
642 piTriList_in_and_out[i] = piTriList_in_and_out[i2rec];
643 }
644 }
645 else
646 {
647 int iL=iL_in, iR=iR_in;
648 assert((iR_in-iL_in)>0); // at least 2 entries
649
650 // separate (by fSep) all points between iL_in and iR_in in pTmpVert[]
651 while (iL < iR)
652 {
653 tbool bReadyLeftSwap = TFALSE, bReadyRightSwap = TFALSE;
654 while ((!bReadyLeftSwap) && iL<iR)
655 {
656 assert(iL>=iL_in && iL<=iR_in);
657 bReadyLeftSwap = !(pTmpVert[iL].vert[channel]<fSep);
658 if (!bReadyLeftSwap) ++iL;
659 }
660 while ((!bReadyRightSwap) && iL<iR)
661 {
662 assert(iR>=iL_in && iR<=iR_in);
663 bReadyRightSwap = pTmpVert[iR].vert[channel]<fSep;
664 if (!bReadyRightSwap) --iR;
665 }
666 assert( (iL<iR) || !(bReadyLeftSwap && bReadyRightSwap) );
667
668 if (bReadyLeftSwap && bReadyRightSwap)
669 {
670 const STmpVert sTmp = pTmpVert[iL];
671 assert(iL<iR);
672 pTmpVert[iL] = pTmpVert[iR];
673 pTmpVert[iR] = sTmp;
674 ++iL; --iR;
675 }
676 }
677
678 assert(iL==(iR+1) || (iL==iR));
679 if (iL==iR)
680 {
681 const tbool bReadyRightSwap = pTmpVert[iR].vert[channel]<fSep;
682 if (bReadyRightSwap) ++iL;
683 else --iR;
684 }
685
686 // only need to weld when there is more than 1 instance of the (x,y,z)
687 if (iL_in < iR)
688 MergeVertsFast(piTriList_in_and_out, pTmpVert, pContext, iL_in, iR); // weld all left of fSep
689 if (iL < iR_in)
690 MergeVertsFast(piTriList_in_and_out, pTmpVert, pContext, iL, iR_in); // weld all right of (or equal to) fSep
691 }
692}
693
694static void MergeVertsSlow(int piTriList_in_and_out[], const SMikkTSpaceContext * pContext, const int pTable[], const int iEntries)
695{
696 // this can be optimized further using a tree structure or more hashing.
697 int e=0;
698 for (e=0; e<iEntries; e++)
699 {
700 int i = pTable[e];
701 const int index = piTriList_in_and_out[i];
702 const SVec3 vP = GetPosition(pContext, index);
703 const SVec3 vN = GetNormal(pContext, index);
704 const SVec3 vT = GetTexCoord(pContext, index);
705
706 tbool bNotFound = TTRUE;
707 int e2=0, i2rec=-1;
708 while (e2<e && bNotFound)
709 {
710 const int i2 = pTable[e2];
711 const int index2 = piTriList_in_and_out[i2];
712 const SVec3 vP2 = GetPosition(pContext, index2);
713 const SVec3 vN2 = GetNormal(pContext, index2);
714 const SVec3 vT2 = GetTexCoord(pContext, index2);
715 i2rec = i2;
716
717 if (veq(vP,vP2) && veq(vN,vN2) && veq(vT,vT2))
718 bNotFound = TFALSE;
719 else
720 ++e2;
721 }
722
723 // merge if previously found
724 if (!bNotFound)
725 piTriList_in_and_out[i] = piTriList_in_and_out[i2rec];
726 }
727}
728
729static void GenerateSharedVerticesIndexListSlow(int piTriList_in_and_out[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn)
730{
731 int iNumUniqueVerts = 0, t=0, i=0;
732 for (t=0; t<iNrTrianglesIn; t++)
733 {
734 for (i=0; i<3; i++)
735 {
736 const int offs = t*3 + i;
737 const int index = piTriList_in_and_out[offs];
738
739 const SVec3 vP = GetPosition(pContext, index);
740 const SVec3 vN = GetNormal(pContext, index);
741 const SVec3 vT = GetTexCoord(pContext, index);
742
743 tbool bFound = TFALSE;
744 int t2=0, index2rec=-1;
745 while (!bFound && t2<=t)
746 {
747 int j=0;
748 while (!bFound && j<3)
749 {
750 const int index2 = piTriList_in_and_out[t2*3 + j];
751 const SVec3 vP2 = GetPosition(pContext, index2);
752 const SVec3 vN2 = GetNormal(pContext, index2);
753 const SVec3 vT2 = GetTexCoord(pContext, index2);
754
755 if (veq(vP,vP2) && veq(vN,vN2) && veq(vT,vT2))
756 bFound = TTRUE;
757 else
758 ++j;
759 }
760 if (!bFound) ++t2;
761 }
762
763 assert(bFound);
764 // if we found our own
765 if (index2rec == index) { ++iNumUniqueVerts; }
766
767 piTriList_in_and_out[offs] = index2rec;
768 }
769 }
770}
771
772static int GenerateInitialVerticesIndexList(STriInfo pTriInfos[], int piTriList_out[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn)
773{
774 int iTSpacesOffs = 0, f=0, t=0;
775 int iDstTriIndex = 0;
776 for (f=0; f<pContext->m_pInterface->m_getNumFaces(pContext); f++)
777 {
778 const int verts = pContext->m_pInterface->m_getNumVerticesOfFace(pContext, f);
779 if (verts!=3 && verts!=4) continue;
780
781 pTriInfos[iDstTriIndex].iOrgFaceNumber = f;
782 pTriInfos[iDstTriIndex].iTSpacesOffs = iTSpacesOffs;
783
784 if (verts==3)
785 {
786 unsigned char * pVerts = pTriInfos[iDstTriIndex].vert_num;
787 pVerts[0]=0; pVerts[1]=1; pVerts[2]=2;
788 piTriList_out[iDstTriIndex*3+0] = MakeIndex(f, 0);
789 piTriList_out[iDstTriIndex*3+1] = MakeIndex(f, 1);
790 piTriList_out[iDstTriIndex*3+2] = MakeIndex(f, 2);
791 ++iDstTriIndex; // next
792 }
793 else
794 {
795 {
796 pTriInfos[iDstTriIndex+1].iOrgFaceNumber = f;
797 pTriInfos[iDstTriIndex+1].iTSpacesOffs = iTSpacesOffs;
798 }
799
800 {
801 // need an order independent way to evaluate
802 // tspace on quads. This is done by splitting
803 // along the shortest diagonal.
804 const int i0 = MakeIndex(f, 0);
805 const int i1 = MakeIndex(f, 1);
806 const int i2 = MakeIndex(f, 2);
807 const int i3 = MakeIndex(f, 3);
808 const SVec3 T0 = GetTexCoord(pContext, i0);
809 const SVec3 T1 = GetTexCoord(pContext, i1);
810 const SVec3 T2 = GetTexCoord(pContext, i2);
811 const SVec3 T3 = GetTexCoord(pContext, i3);
812 const float distSQ_02 = LengthSquared(vsub(T2,T0));
813 const float distSQ_13 = LengthSquared(vsub(T3,T1));
814 tbool bQuadDiagIs_02;
815 if (distSQ_02<distSQ_13)
816 bQuadDiagIs_02 = TTRUE;
817 else if (distSQ_13<distSQ_02)
818 bQuadDiagIs_02 = TFALSE;
819 else
820 {
821 const SVec3 P0 = GetPosition(pContext, i0);
822 const SVec3 P1 = GetPosition(pContext, i1);
823 const SVec3 P2 = GetPosition(pContext, i2);
824 const SVec3 P3 = GetPosition(pContext, i3);
825 const float distSQ_02 = LengthSquared(vsub(P2,P0));
826 const float distSQ_13 = LengthSquared(vsub(P3,P1));
827
828 bQuadDiagIs_02 = distSQ_13<distSQ_02 ? TFALSE : TTRUE;
829 }
830
831 if (bQuadDiagIs_02)
832 {
833 {
834 unsigned char * pVerts_A = pTriInfos[iDstTriIndex].vert_num;
835 pVerts_A[0]=0; pVerts_A[1]=1; pVerts_A[2]=2;
836 }
837 piTriList_out[iDstTriIndex*3+0] = i0;
838 piTriList_out[iDstTriIndex*3+1] = i1;
839 piTriList_out[iDstTriIndex*3+2] = i2;
840 ++iDstTriIndex; // next
841 {
842 unsigned char * pVerts_B = pTriInfos[iDstTriIndex].vert_num;
843 pVerts_B[0]=0; pVerts_B[1]=2; pVerts_B[2]=3;
844 }
845 piTriList_out[iDstTriIndex*3+0] = i0;
846 piTriList_out[iDstTriIndex*3+1] = i2;
847 piTriList_out[iDstTriIndex*3+2] = i3;
848 ++iDstTriIndex; // next
849 }
850 else
851 {
852 {
853 unsigned char * pVerts_A = pTriInfos[iDstTriIndex].vert_num;
854 pVerts_A[0]=0; pVerts_A[1]=1; pVerts_A[2]=3;
855 }
856 piTriList_out[iDstTriIndex*3+0] = i0;
857 piTriList_out[iDstTriIndex*3+1] = i1;
858 piTriList_out[iDstTriIndex*3+2] = i3;
859 ++iDstTriIndex; // next
860 {
861 unsigned char * pVerts_B = pTriInfos[iDstTriIndex].vert_num;
862 pVerts_B[0]=1; pVerts_B[1]=2; pVerts_B[2]=3;
863 }
864 piTriList_out[iDstTriIndex*3+0] = i1;
865 piTriList_out[iDstTriIndex*3+1] = i2;
866 piTriList_out[iDstTriIndex*3+2] = i3;
867 ++iDstTriIndex; // next
868 }
869 }
870 }
871
872 iTSpacesOffs += verts;
873 assert(iDstTriIndex<=iNrTrianglesIn);
874 }
875
876 for (t=0; t<iNrTrianglesIn; t++)
877 pTriInfos[t].iFlag = 0;
878
879 // return total amount of tspaces
880 return iTSpacesOffs;
881}
882
883static SVec3 GetPosition(const SMikkTSpaceContext * pContext, const int index)
884{
885 int iF, iI;
886 SVec3 res; float pos[3];
887 IndexToData(&iF, &iI, index);
888 pContext->m_pInterface->m_getPosition(pContext, pos, iF, iI);
889 res.x=pos[0]; res.y=pos[1]; res.z=pos[2];
890 return res;
891}
892
893static SVec3 GetNormal(const SMikkTSpaceContext * pContext, const int index)
894{
895 int iF, iI;
896 SVec3 res; float norm[3];
897 IndexToData(&iF, &iI, index);
898 pContext->m_pInterface->m_getNormal(pContext, norm, iF, iI);
899 res.x=norm[0]; res.y=norm[1]; res.z=norm[2];
900 return res;
901}
902
903static SVec3 GetTexCoord(const SMikkTSpaceContext * pContext, const int index)
904{
905 int iF, iI;
906 SVec3 res; float texc[2];
907 IndexToData(&iF, &iI, index);
908 pContext->m_pInterface->m_getTexCoord(pContext, texc, iF, iI);
909 res.x=texc[0]; res.y=texc[1]; res.z=1.0f;
910 return res;
911}
912
913/////////////////////////////////////////////////////////////////////////////////////////////////////
914/////////////////////////////////////////////////////////////////////////////////////////////////////
915
916typedef union {
917 struct
918 {
919 int i0, i1, f;
920 };
921 int array[3];
922} SEdge;
923
924static void BuildNeighborsFast(STriInfo pTriInfos[], SEdge * pEdges, const int piTriListIn[], const int iNrTrianglesIn);
925static void BuildNeighborsSlow(STriInfo pTriInfos[], const int piTriListIn[], const int iNrTrianglesIn);
926
927// returns the texture area times 2
928static float CalcTexArea(const SMikkTSpaceContext * pContext, const int indices[])
929{
930 const SVec3 t1 = GetTexCoord(pContext, indices[0]);
931 const SVec3 t2 = GetTexCoord(pContext, indices[1]);
932 const SVec3 t3 = GetTexCoord(pContext, indices[2]);
933
934 const float t21x = t2.x-t1.x;
935 const float t21y = t2.y-t1.y;
936 const float t31x = t3.x-t1.x;
937 const float t31y = t3.y-t1.y;
938
939 const float fSignedAreaSTx2 = t21x*t31y - t21y*t31x;
940
941 return fSignedAreaSTx2<0 ? (-fSignedAreaSTx2) : fSignedAreaSTx2;
942}
943
944static void InitTriInfo(STriInfo pTriInfos[], const int piTriListIn[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn)
945{
946 int f=0, i=0, t=0;
947 // pTriInfos[f].iFlag is cleared in GenerateInitialVerticesIndexList() which is called before this function.
948
949 // generate neighbor info list
950 for (f=0; f<iNrTrianglesIn; f++)
951 for (i=0; i<3; i++)
952 {
953 pTriInfos[f].FaceNeighbors[i] = -1;
954 pTriInfos[f].AssignedGroup[i] = NULL;
955
956 pTriInfos[f].vOs.x=0.0f; pTriInfos[f].vOs.y=0.0f; pTriInfos[f].vOs.z=0.0f;
957 pTriInfos[f].vOt.x=0.0f; pTriInfos[f].vOt.y=0.0f; pTriInfos[f].vOt.z=0.0f;
958 pTriInfos[f].fMagS = 0;
959 pTriInfos[f].fMagT = 0;
960
961 // assumed bad
962 pTriInfos[f].iFlag |= GROUP_WITH_ANY;
963 }
964
965 // evaluate first order derivatives
966 for (f=0; f<iNrTrianglesIn; f++)
967 {
968 // initial values
969 const SVec3 v1 = GetPosition(pContext, piTriListIn[f*3+0]);
970 const SVec3 v2 = GetPosition(pContext, piTriListIn[f*3+1]);
971 const SVec3 v3 = GetPosition(pContext, piTriListIn[f*3+2]);
972 const SVec3 t1 = GetTexCoord(pContext, piTriListIn[f*3+0]);
973 const SVec3 t2 = GetTexCoord(pContext, piTriListIn[f*3+1]);
974 const SVec3 t3 = GetTexCoord(pContext, piTriListIn[f*3+2]);
975
976 const float t21x = t2.x-t1.x;
977 const float t21y = t2.y-t1.y;
978 const float t31x = t3.x-t1.x;
979 const float t31y = t3.y-t1.y;
980 const SVec3 d1 = vsub(v2,v1);
981 const SVec3 d2 = vsub(v3,v1);
982
983 const float fSignedAreaSTx2 = t21x*t31y - t21y*t31x;
984 //assert(fSignedAreaSTx2!=0);
985 SVec3 vOs = vsub(vscale(t31y,d1), vscale(t21y,d2)); // eq 18
986 SVec3 vOt = vadd(vscale(-t31x,d1), vscale(t21x,d2)); // eq 19
987
988 pTriInfos[f].iFlag |= (fSignedAreaSTx2>0 ? ORIENT_PRESERVING : 0);
989
990 if ( NotZero(fSignedAreaSTx2) )
991 {
992 const float fAbsArea = fabsf(fSignedAreaSTx2);
993 const float fLenOs = Length(vOs);
994 const float fLenOt = Length(vOt);
995 const float fS = (pTriInfos[f].iFlag&ORIENT_PRESERVING)==0 ? (-1.0f) : 1.0f;
996 if ( NotZero(fLenOs) ) pTriInfos[f].vOs = vscale(fS/fLenOs, vOs);
997 if ( NotZero(fLenOt) ) pTriInfos[f].vOt = vscale(fS/fLenOt, vOt);
998
999 // evaluate magnitudes prior to normalization of vOs and vOt
1000 pTriInfos[f].fMagS = fLenOs / fAbsArea;
1001 pTriInfos[f].fMagT = fLenOt / fAbsArea;
1002
1003 // if this is a good triangle
1004 if ( NotZero(pTriInfos[f].fMagS) && NotZero(pTriInfos[f].fMagT))
1005 pTriInfos[f].iFlag &= (~GROUP_WITH_ANY);
1006 }
1007 }
1008
1009 // force otherwise healthy quads to a fixed orientation
1010 while (t<(iNrTrianglesIn-1))
1011 {
1012 const int iFO_a = pTriInfos[t].iOrgFaceNumber;
1013 const int iFO_b = pTriInfos[t+1].iOrgFaceNumber;
1014 if (iFO_a==iFO_b) // this is a quad
1015 {
1016 const tbool bIsDeg_a = (pTriInfos[t].iFlag&MARK_DEGENERATE)!=0 ? TTRUE : TFALSE;
1017 const tbool bIsDeg_b = (pTriInfos[t+1].iFlag&MARK_DEGENERATE)!=0 ? TTRUE : TFALSE;
1018
1019 // bad triangles should already have been removed by
1020 // DegenPrologue(), but just in case check bIsDeg_a and bIsDeg_a are false
1021 if ((bIsDeg_a||bIsDeg_b)==TFALSE)
1022 {
1023 const tbool bOrientA = (pTriInfos[t].iFlag&ORIENT_PRESERVING)!=0 ? TTRUE : TFALSE;
1024 const tbool bOrientB = (pTriInfos[t+1].iFlag&ORIENT_PRESERVING)!=0 ? TTRUE : TFALSE;
1025 // if this happens the quad has extremely bad mapping!!
1026 if (bOrientA!=bOrientB)
1027 {
1028 //printf("found quad with bad mapping\n");
1029 tbool bChooseOrientFirstTri = TFALSE;
1030 if ((pTriInfos[t+1].iFlag&GROUP_WITH_ANY)!=0) bChooseOrientFirstTri = TTRUE;
1031 else if ( CalcTexArea(pContext, &piTriListIn[t*3+0]) >= CalcTexArea(pContext, &piTriListIn[(t+1)*3+0]) )
1032 bChooseOrientFirstTri = TTRUE;
1033
1034 // force match
1035 {
1036 const int t0 = bChooseOrientFirstTri ? t : (t+1);
1037 const int t1 = bChooseOrientFirstTri ? (t+1) : t;
1038 pTriInfos[t1].iFlag &= (~ORIENT_PRESERVING); // clear first
1039 pTriInfos[t1].iFlag |= (pTriInfos[t0].iFlag&ORIENT_PRESERVING); // copy bit
1040 }
1041 }
1042 }
1043 t += 2;
1044 }
1045 else
1046 ++t;
1047 }
1048
1049 // match up edge pairs
1050 {
1051 SEdge * pEdges = (SEdge *) malloc(sizeof(SEdge)*iNrTrianglesIn*3);
1052 if (pEdges==NULL)
1053 BuildNeighborsSlow(pTriInfos, piTriListIn, iNrTrianglesIn);
1054 else
1055 {
1056 BuildNeighborsFast(pTriInfos, pEdges, piTriListIn, iNrTrianglesIn);
1057
1058 free(pEdges);
1059 }
1060 }
1061}
1062
1063/////////////////////////////////////////////////////////////////////////////////////////////////////
1064/////////////////////////////////////////////////////////////////////////////////////////////////////
1065
1066static tbool AssignRecur(const int piTriListIn[], STriInfo psTriInfos[], const int iMyTriIndex, SGroup * pGroup);
1067static void AddTriToGroup(SGroup * pGroup, const int iTriIndex);
1068
1069static int Build4RuleGroups(STriInfo pTriInfos[], SGroup pGroups[], int piGroupTrianglesBuffer[], const int piTriListIn[], const int iNrTrianglesIn)
1070{
1071 const int iNrMaxGroups = iNrTrianglesIn*3;
1072 int iNrActiveGroups = 0;
1073 int iOffset = 0, f=0, i=0;
1074 (void)iNrMaxGroups; /* quiet warnings in non debug mode */
1075 for (f=0; f<iNrTrianglesIn; f++)
1076 {
1077 for (i=0; i<3; i++)
1078 {
1079 // if not assigned to a group
1080 if ((pTriInfos[f].iFlag&GROUP_WITH_ANY)==0 && pTriInfos[f].AssignedGroup[i]==NULL)
1081 {
1082 tbool bOrPre;
1083 int neigh_indexL, neigh_indexR;
1084 const int vert_index = piTriListIn[f*3+i];
1085 assert(iNrActiveGroups<iNrMaxGroups);
1086 pTriInfos[f].AssignedGroup[i] = &pGroups[iNrActiveGroups];
1087 pTriInfos[f].AssignedGroup[i]->iVertexRepresentitive = vert_index;
1088 pTriInfos[f].AssignedGroup[i]->bOrientPreservering = (pTriInfos[f].iFlag&ORIENT_PRESERVING)!=0;
1089 pTriInfos[f].AssignedGroup[i]->iNrFaces = 0;
1090 pTriInfos[f].AssignedGroup[i]->pFaceIndices = &piGroupTrianglesBuffer[iOffset];
1091 ++iNrActiveGroups;
1092
1093 AddTriToGroup(pTriInfos[f].AssignedGroup[i], f);
1094 bOrPre = (pTriInfos[f].iFlag&ORIENT_PRESERVING)!=0 ? TTRUE : TFALSE;
1095 neigh_indexL = pTriInfos[f].FaceNeighbors[i];
1096 neigh_indexR = pTriInfos[f].FaceNeighbors[i>0?(i-1):2];
1097 if (neigh_indexL>=0) // neighbor
1098 {
1099 const tbool bAnswer =
1100 AssignRecur(piTriListIn, pTriInfos, neigh_indexL,
1101 pTriInfos[f].AssignedGroup[i] );
1102
1103 const tbool bOrPre2 = (pTriInfos[neigh_indexL].iFlag&ORIENT_PRESERVING)!=0 ? TTRUE : TFALSE;
1104 const tbool bDiff = bOrPre!=bOrPre2 ? TTRUE : TFALSE;
1105 assert(bAnswer || bDiff);
1106 (void)bAnswer, (void)bDiff; /* quiet warnings in non debug mode */
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 (void)bAnswer, (void)bDiff; /* quiet warnings in non debug mode */
1118 }
1119
1120 // update offset
1121 iOffset += pTriInfos[f].AssignedGroup[i]->iNrFaces;
1122 // since the groups are disjoint a triangle can never
1123 // belong to more than 3 groups. Subsequently something
1124 // is completely screwed if this assertion ever hits.
1125 assert(iOffset <= iNrMaxGroups);
1126 }
1127 }
1128 }
1129
1130 return iNrActiveGroups;
1131}
1132
1133static void AddTriToGroup(SGroup * pGroup, const int iTriIndex)
1134{
1135 pGroup->pFaceIndices[pGroup->iNrFaces] = iTriIndex;
1136 ++pGroup->iNrFaces;
1137}
1138
1139static tbool AssignRecur(const int piTriListIn[], STriInfo psTriInfos[],
1140 const int iMyTriIndex, SGroup * pGroup)
1141{
1142 STriInfo * pMyTriInfo = &psTriInfos[iMyTriIndex];
1143
1144 // track down vertex
1145 const int iVertRep = pGroup->iVertexRepresentitive;
1146 const int * pVerts = &piTriListIn[3*iMyTriIndex+0];
1147 int i=-1;
1148 if (pVerts[0]==iVertRep) i=0;
1149 else if (pVerts[1]==iVertRep) i=1;
1150 else if (pVerts[2]==iVertRep) i=2;
1151 assert(i>=0 && i<3);
1152
1153 // early out
1154 if (pMyTriInfo->AssignedGroup[i] == pGroup) return TTRUE;
1155 else if (pMyTriInfo->AssignedGroup[i]!=NULL) return TFALSE;
1156 if ((pMyTriInfo->iFlag&GROUP_WITH_ANY)!=0)
1157 {
1158 // first to group with a group-with-anything triangle
1159 // determines it's orientation.
1160 // This is the only existing order dependency in the code!!
1161 if ( pMyTriInfo->AssignedGroup[0] == NULL &&
1162 pMyTriInfo->AssignedGroup[1] == NULL &&
1163 pMyTriInfo->AssignedGroup[2] == NULL )
1164 {
1165 pMyTriInfo->iFlag &= (~ORIENT_PRESERVING);
1166 pMyTriInfo->iFlag |= (pGroup->bOrientPreservering ? ORIENT_PRESERVING : 0);
1167 }
1168 }
1169 {
1170 const tbool bOrient = (pMyTriInfo->iFlag&ORIENT_PRESERVING)!=0 ? TTRUE : TFALSE;
1171 if (bOrient != pGroup->bOrientPreservering) return TFALSE;
1172 }
1173
1174 AddTriToGroup(pGroup, iMyTriIndex);
1175 pMyTriInfo->AssignedGroup[i] = pGroup;
1176
1177 {
1178 const int neigh_indexL = pMyTriInfo->FaceNeighbors[i];
1179 const int neigh_indexR = pMyTriInfo->FaceNeighbors[i>0?(i-1):2];
1180 if (neigh_indexL>=0)
1181 AssignRecur(piTriListIn, psTriInfos, neigh_indexL, pGroup);
1182 if (neigh_indexR>=0)
1183 AssignRecur(piTriListIn, psTriInfos, neigh_indexR, pGroup);
1184 }
1185
1186
1187
1188 return TTRUE;
1189}
1190
1191/////////////////////////////////////////////////////////////////////////////////////////////////////
1192/////////////////////////////////////////////////////////////////////////////////////////////////////
1193
1194static tbool CompareSubGroups(const SSubGroup * pg1, const SSubGroup * pg2);
1195static void QuickSort(int* pSortBuffer, int iLeft, int iRight, unsigned int uSeed);
1196static STSpace EvalTspace(int face_indices[], const int iFaces, const int piTriListIn[], const STriInfo pTriInfos[], const SMikkTSpaceContext * pContext, const int iVertexRepresentitive);
1197
1198static tbool GenerateTSpaces(STSpace psTspace[], const STriInfo pTriInfos[], const SGroup pGroups[],
1199 const int iNrActiveGroups, const int piTriListIn[], const float fThresCos,
1200 const SMikkTSpaceContext * pContext)
1201{
1202 STSpace * pSubGroupTspace = NULL;
1203 SSubGroup * pUniSubGroups = NULL;
1204 int * pTmpMembers = NULL;
1205 int iMaxNrFaces=0, iUniqueTspaces=0, g=0, i=0;
1206 for (g=0; g<iNrActiveGroups; g++)
1207 if (iMaxNrFaces < pGroups[g].iNrFaces)
1208 iMaxNrFaces = pGroups[g].iNrFaces;
1209
1210 if (iMaxNrFaces == 0) return TTRUE;
1211
1212 // make initial allocations
1213 pSubGroupTspace = (STSpace *) malloc(sizeof(STSpace)*iMaxNrFaces);
1214 pUniSubGroups = (SSubGroup *) malloc(sizeof(SSubGroup)*iMaxNrFaces);
1215 pTmpMembers = (int *) malloc(sizeof(int)*iMaxNrFaces);
1216 if (pSubGroupTspace==NULL || pUniSubGroups==NULL || pTmpMembers==NULL)
1217 {
1218 if (pSubGroupTspace!=NULL) free(pSubGroupTspace);
1219 if (pUniSubGroups!=NULL) free(pUniSubGroups);
1220 if (pTmpMembers!=NULL) free(pTmpMembers);
1221 return TFALSE;
1222 }
1223
1224
1225 iUniqueTspaces = 0;
1226 for (g=0; g<iNrActiveGroups; g++)
1227 {
1228 const SGroup * pGroup = &pGroups[g];
1229 int iUniqueSubGroups = 0, s=0;
1230
1231 for (i=0; i<pGroup->iNrFaces; i++) // triangles
1232 {
1233 const int f = pGroup->pFaceIndices[i]; // triangle number
1234 int index=-1, iVertIndex=-1, iOF_1=-1, iMembers=0, j=0, l=0;
1235 SSubGroup tmp_group;
1236 tbool bFound;
1237 SVec3 n, vOs, vOt;
1238 if (pTriInfos[f].AssignedGroup[0]==pGroup) index=0;
1239 else if (pTriInfos[f].AssignedGroup[1]==pGroup) index=1;
1240 else if (pTriInfos[f].AssignedGroup[2]==pGroup) index=2;
1241 assert(index>=0 && index<3);
1242
1243 iVertIndex = piTriListIn[f*3+index];
1244 assert(iVertIndex==pGroup->iVertexRepresentitive);
1245
1246 // is normalized already
1247 n = GetNormal(pContext, iVertIndex);
1248
1249 // project
1250 vOs = vsub(pTriInfos[f].vOs, vscale(vdot(n,pTriInfos[f].vOs), n));
1251 vOt = vsub(pTriInfos[f].vOt, vscale(vdot(n,pTriInfos[f].vOt), n));
1252 if ( VNotZero(vOs) ) vOs = Normalize(vOs);
1253 if ( VNotZero(vOt) ) vOt = Normalize(vOt);
1254
1255 // original face number
1256 iOF_1 = pTriInfos[f].iOrgFaceNumber;
1257
1258 iMembers = 0;
1259 for (j=0; j<pGroup->iNrFaces; j++)
1260 {
1261 const int t = pGroup->pFaceIndices[j]; // triangle number
1262 const int iOF_2 = pTriInfos[t].iOrgFaceNumber;
1263
1264 // project
1265 SVec3 vOs2 = vsub(pTriInfos[t].vOs, vscale(vdot(n,pTriInfos[t].vOs), n));
1266 SVec3 vOt2 = vsub(pTriInfos[t].vOt, vscale(vdot(n,pTriInfos[t].vOt), n));
1267 if ( VNotZero(vOs2) ) vOs2 = Normalize(vOs2);
1268 if ( VNotZero(vOt2) ) vOt2 = Normalize(vOt2);
1269
1270 {
1271 const tbool bAny = ( (pTriInfos[f].iFlag | pTriInfos[t].iFlag) & GROUP_WITH_ANY )!=0 ? TTRUE : TFALSE;
1272 // make sure triangles which belong to the same quad are joined.
1273 const tbool bSameOrgFace = iOF_1==iOF_2 ? TTRUE : TFALSE;
1274
1275 const float fCosS = vdot(vOs,vOs2);
1276 const float fCosT = vdot(vOt,vOt2);
1277
1278 assert(f!=t || bSameOrgFace); // sanity check
1279 if (bAny || bSameOrgFace || (fCosS>fThresCos && fCosT>fThresCos))
1280 pTmpMembers[iMembers++] = t;
1281 }
1282 }
1283
1284 // sort pTmpMembers
1285 tmp_group.iNrFaces = iMembers;
1286 tmp_group.pTriMembers = pTmpMembers;
1287 if (iMembers>1)
1288 {
1289 unsigned int uSeed = INTERNAL_RND_SORT_SEED; // could replace with a random seed?
1290 QuickSort(pTmpMembers, 0, iMembers-1, uSeed);
1291 }
1292
1293 // look for an existing match
1294 bFound = TFALSE;
1295 l=0;
1296 while (l<iUniqueSubGroups && !bFound)
1297 {
1298 bFound = CompareSubGroups(&tmp_group, &pUniSubGroups[l]);
1299 if (!bFound) ++l;
1300 }
1301
1302 // assign tangent space index
1303 assert(bFound || l==iUniqueSubGroups);
1304 //piTempTangIndices[f*3+index] = iUniqueTspaces+l;
1305
1306 // if no match was found we allocate a new subgroup
1307 if (!bFound)
1308 {
1309 // insert new subgroup
1310 int * pIndices = (int *) malloc(sizeof(int)*iMembers);
1311 if (pIndices==NULL)
1312 {
1313 // clean up and return false
1314 int s=0;
1315 for (s=0; s<iUniqueSubGroups; s++)
1316 free(pUniSubGroups[s].pTriMembers);
1317 free(pUniSubGroups);
1318 free(pTmpMembers);
1319 free(pSubGroupTspace);
1320 return TFALSE;
1321 }
1322 pUniSubGroups[iUniqueSubGroups].iNrFaces = iMembers;
1323 pUniSubGroups[iUniqueSubGroups].pTriMembers = pIndices;
1324 memcpy(pIndices, tmp_group.pTriMembers, iMembers*sizeof(int));
1325 pSubGroupTspace[iUniqueSubGroups] =
1326 EvalTspace(tmp_group.pTriMembers, iMembers, piTriListIn, pTriInfos, pContext, pGroup->iVertexRepresentitive);
1327 ++iUniqueSubGroups;
1328 }
1329
1330 // output tspace
1331 {
1332 const int iOffs = pTriInfos[f].iTSpacesOffs;
1333 const int iVert = pTriInfos[f].vert_num[index];
1334 STSpace * pTS_out = &psTspace[iOffs+iVert];
1335 assert(pTS_out->iCounter<2);
1336 assert(((pTriInfos[f].iFlag&ORIENT_PRESERVING)!=0) == pGroup->bOrientPreservering);
1337 if (pTS_out->iCounter==1)
1338 {
1339 *pTS_out = AvgTSpace(pTS_out, &pSubGroupTspace[l]);
1340 pTS_out->iCounter = 2; // update counter
1341 pTS_out->bOrient = pGroup->bOrientPreservering;
1342 }
1343 else
1344 {
1345 assert(pTS_out->iCounter==0);
1346 *pTS_out = pSubGroupTspace[l];
1347 pTS_out->iCounter = 1; // update counter
1348 pTS_out->bOrient = pGroup->bOrientPreservering;
1349 }
1350 }
1351 }
1352
1353 // clean up and offset iUniqueTspaces
1354 for (s=0; s<iUniqueSubGroups; s++)
1355 free(pUniSubGroups[s].pTriMembers);
1356 iUniqueTspaces += iUniqueSubGroups;
1357 }
1358
1359 // clean up
1360 free(pUniSubGroups);
1361 free(pTmpMembers);
1362 free(pSubGroupTspace);
1363
1364 return TTRUE;
1365}
1366
1367static 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 = (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
1441static 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
1454static 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
1498static void QuickSortEdges(SEdge * pSortBuffer, int iLeft, int iRight, const int channel, unsigned int uSeed);
1499static void GetEdge(int * i0_out, int * i1_out, int * edgenum_out, const int indices[], const int i0_in, const int i1_in);
1500
1501static 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
1596static 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
1645static 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;
1672 iR = iRight;
1673 n = (iR-iL)+1;
1674 assert(n>=0);
1675 index = (int) (uSeed%n);
1676
1677 iMid=pSortBuffer[index + iL].array[channel];
1678
1679 do
1680 {
1681 while (pSortBuffer[iL].array[channel] < iMid)
1682 ++iL;
1683 while (pSortBuffer[iR].array[channel] > iMid)
1684 --iR;
1685
1686 if (iL <= iR)
1687 {
1688 sTmp = pSortBuffer[iL];
1689 pSortBuffer[iL] = pSortBuffer[iR];
1690 pSortBuffer[iR] = sTmp;
1691 ++iL; --iR;
1692 }
1693 }
1694 while (iL <= iR);
1695
1696 if (iLeft < iR)
1697 QuickSortEdges(pSortBuffer, iLeft, iR, channel, uSeed);
1698 if (iL < iRight)
1699 QuickSortEdges(pSortBuffer, iL, iRight, channel, uSeed);
1700}
1701
1702// resolve ordering and edge number
1703static void GetEdge(int * i0_out, int * i1_out, int * edgenum_out, const int indices[], const int i0_in, const int i1_in)
1704{
1705 *edgenum_out = -1;
1706
1707 // test if first index is on the edge
1708 if (indices[0]==i0_in || indices[0]==i1_in)
1709 {
1710 // test if second index is on the edge
1711 if (indices[1]==i0_in || indices[1]==i1_in)
1712 {
1713 edgenum_out[0]=0; // first edge
1714 i0_out[0]=indices[0];
1715 i1_out[0]=indices[1];
1716 }
1717 else
1718 {
1719 edgenum_out[0]=2; // third edge
1720 i0_out[0]=indices[2];
1721 i1_out[0]=indices[0];
1722 }
1723 }
1724 else
1725 {
1726 // only second and third index is on the edge
1727 edgenum_out[0]=1; // second edge
1728 i0_out[0]=indices[1];
1729 i1_out[0]=indices[2];
1730 }
1731}
1732
1733
1734/////////////////////////////////////////////////////////////////////////////////////////////
1735/////////////////////////////////// Degenerate triangles ////////////////////////////////////
1736
1737static void DegenPrologue(STriInfo pTriInfos[], int piTriList_out[], const int iNrTrianglesIn, const int iTotTris)
1738{
1739 int iNextGoodTriangleSearchIndex=-1;
1740 tbool bStillFindingGoodOnes;
1741
1742 // locate quads with only one good triangle
1743 int t=0;
1744 while (t<(iTotTris-1))
1745 {
1746 const int iFO_a = pTriInfos[t].iOrgFaceNumber;
1747 const int iFO_b = pTriInfos[t+1].iOrgFaceNumber;
1748 if (iFO_a==iFO_b) // this is a quad
1749 {
1750 const tbool bIsDeg_a = (pTriInfos[t].iFlag&MARK_DEGENERATE)!=0 ? TTRUE : TFALSE;
1751 const tbool bIsDeg_b = (pTriInfos[t+1].iFlag&MARK_DEGENERATE)!=0 ? TTRUE : TFALSE;
1752 if ((bIsDeg_a^bIsDeg_b)!=0)
1753 {
1754 pTriInfos[t].iFlag |= QUAD_ONE_DEGEN_TRI;
1755 pTriInfos[t+1].iFlag |= QUAD_ONE_DEGEN_TRI;
1756 }
1757 t += 2;
1758 }
1759 else
1760 ++t;
1761 }
1762
1763 // reorder list so all degen triangles are moved to the back
1764 // without reordering the good triangles
1765 iNextGoodTriangleSearchIndex = 1;
1766 t=0;
1767 bStillFindingGoodOnes = TTRUE;
1768 while (t<iNrTrianglesIn && bStillFindingGoodOnes)
1769 {
1770 const tbool bIsGood = (pTriInfos[t].iFlag&MARK_DEGENERATE)==0 ? TTRUE : TFALSE;
1771 if (bIsGood)
1772 {
1773 if (iNextGoodTriangleSearchIndex < (t+2))
1774 iNextGoodTriangleSearchIndex = t+2;
1775 }
1776 else
1777 {
1778 int t0, t1;
1779 // search for the first good triangle.
1780 tbool bJustADegenerate = TTRUE;
1781 while (bJustADegenerate && iNextGoodTriangleSearchIndex<iTotTris)
1782 {
1783 const tbool bIsGood = (pTriInfos[iNextGoodTriangleSearchIndex].iFlag&MARK_DEGENERATE)==0 ? TTRUE : TFALSE;
1784 if (bIsGood) bJustADegenerate=TFALSE;
1785 else ++iNextGoodTriangleSearchIndex;
1786 }
1787
1788 t0 = t;
1789 t1 = iNextGoodTriangleSearchIndex;
1790 ++iNextGoodTriangleSearchIndex;
1791 assert(iNextGoodTriangleSearchIndex > (t+1));
1792
1793 // swap triangle t0 and t1
1794 if (!bJustADegenerate)
1795 {
1796 int i=0;
1797 for (i=0; i<3; i++)
1798 {
1799 const int index = piTriList_out[t0*3+i];
1800 piTriList_out[t0*3+i] = piTriList_out[t1*3+i];
1801 piTriList_out[t1*3+i] = index;
1802 }
1803 {
1804 const STriInfo tri_info = pTriInfos[t0];
1805 pTriInfos[t0] = pTriInfos[t1];
1806 pTriInfos[t1] = tri_info;
1807 }
1808 }
1809 else
1810 bStillFindingGoodOnes = TFALSE; // this is not supposed to happen
1811 }
1812
1813 if (bStillFindingGoodOnes) ++t;
1814 }
1815
1816 assert(bStillFindingGoodOnes); // code will still work.
1817 assert(iNrTrianglesIn == t);
1818}
1819
1820static void DegenEpilogue(STSpace psTspace[], STriInfo pTriInfos[], int piTriListIn[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn, const int iTotTris)
1821{
1822 int t=0, i=0;
1823 // deal with degenerate triangles
1824 // punishment for degenerate triangles is O(N^2)
1825 for (t=iNrTrianglesIn; t<iTotTris; t++)
1826 {
1827 // degenerate triangles on a quad with one good triangle are skipped
1828 // here but processed in the next loop
1829 const tbool bSkip = (pTriInfos[t].iFlag&QUAD_ONE_DEGEN_TRI)!=0 ? TTRUE : TFALSE;
1830
1831 if (!bSkip)
1832 {
1833 for (i=0; i<3; i++)
1834 {
1835 const int index1 = piTriListIn[t*3+i];
1836 // search through the good triangles
1837 tbool bNotFound = TTRUE;
1838 int j=0;
1839 while (bNotFound && j<(3*iNrTrianglesIn))
1840 {
1841 const int index2 = piTriListIn[j];
1842 if (index1==index2) bNotFound=TFALSE;
1843 else ++j;
1844 }
1845
1846 if (!bNotFound)
1847 {
1848 const int iTri = j/3;
1849 const int iVert = j%3;
1850 const int iSrcVert=pTriInfos[iTri].vert_num[iVert];
1851 const int iSrcOffs=pTriInfos[iTri].iTSpacesOffs;
1852 const int iDstVert=pTriInfos[t].vert_num[i];
1853 const int iDstOffs=pTriInfos[t].iTSpacesOffs;
1854
1855 // copy tspace
1856 psTspace[iDstOffs+iDstVert] = psTspace[iSrcOffs+iSrcVert];
1857 }
1858 }
1859 }
1860 }
1861
1862 // deal with degenerate quads with one good triangle
1863 for (t=0; t<iNrTrianglesIn; t++)
1864 {
1865 // this triangle belongs to a quad where the
1866 // other triangle is degenerate
1867 if ( (pTriInfos[t].iFlag&QUAD_ONE_DEGEN_TRI)!=0 )
1868 {
1869 SVec3 vDstP;
1870 int iOrgF=-1, i=0;
1871 tbool bNotFound;
1872 unsigned char * pV = pTriInfos[t].vert_num;
1873 int iFlag = (1<<pV[0]) | (1<<pV[1]) | (1<<pV[2]);
1874 int iMissingIndex = 0;
1875 if ((iFlag&2)==0) iMissingIndex=1;
1876 else if ((iFlag&4)==0) iMissingIndex=2;
1877 else if ((iFlag&8)==0) iMissingIndex=3;
1878
1879 iOrgF = pTriInfos[t].iOrgFaceNumber;
1880 vDstP = GetPosition(pContext, MakeIndex(iOrgF, iMissingIndex));
1881 bNotFound = TTRUE;
1882 i=0;
1883 while (bNotFound && i<3)
1884 {
1885 const int iVert = pV[i];
1886 const SVec3 vSrcP = GetPosition(pContext, MakeIndex(iOrgF, iVert));
1887 if (veq(vSrcP, vDstP)==TTRUE)
1888 {
1889 const int iOffs = pTriInfos[t].iTSpacesOffs;
1890 psTspace[iOffs+iMissingIndex] = psTspace[iOffs+iVert];
1891 bNotFound=TFALSE;
1892 }
1893 else
1894 ++i;
1895 }
1896 assert(!bNotFound);
1897 }
1898 }
1899}
diff --git a/contrib/cgltf-tangents/MikkTSpace/mikktspace.h b/contrib/cgltf-tangents/MikkTSpace/mikktspace.h
new file mode 100644
index 0000000..52c44a7
--- /dev/null
+++ b/contrib/cgltf-tangents/MikkTSpace/mikktspace.h
@@ -0,0 +1,145 @@
1/** \file mikktspace/mikktspace.h
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#ifndef __MIKKTSPACE_H__
25#define __MIKKTSPACE_H__
26
27
28#ifdef __cplusplus
29extern "C" {
30#endif
31
32/* Author: Morten S. Mikkelsen
33 * Version: 1.0
34 *
35 * The files mikktspace.h and mikktspace.c are designed to be
36 * stand-alone files and it is important that they are kept this way.
37 * Not having dependencies on structures/classes/libraries specific
38 * to the program, in which they are used, allows them to be copied
39 * and used as is into any tool, program or plugin.
40 * The code is designed to consistently generate the same
41 * tangent spaces, for a given mesh, in any tool in which it is used.
42 * This is done by performing an internal welding step and subsequently an order-independent evaluation
43 * of tangent space for meshes consisting of triangles and quads.
44 * This means faces can be received in any order and the same is true for
45 * the order of vertices of each face. The generated result will not be affected
46 * by such reordering. Additionally, whether degenerate (vertices or texture coordinates)
47 * primitives are present or not will not affect the generated results either.
48 * Once tangent space calculation is done the vertices of degenerate primitives will simply
49 * inherit tangent space from neighboring non degenerate primitives.
50 * The analysis behind this implementation can be found in my master's thesis
51 * which is available for download --> http://image.diku.dk/projects/media/morten.mikkelsen.08.pdf
52 * Note that though the tangent spaces at the vertices are generated in an order-independent way,
53 * by this implementation, the interpolated tangent space is still affected by which diagonal is
54 * chosen to split each quad. A sensible solution is to have your tools pipeline always
55 * split quads by the shortest diagonal. This choice is order-independent and works with mirroring.
56 * If these have the same length then compare the diagonals defined by the texture coordinates.
57 * XNormal which is a tool for baking normal maps allows you to write your own tangent space plugin
58 * and also quad triangulator plugin.
59 */
60
61
62typedef int tbool;
63typedef struct SMikkTSpaceContext SMikkTSpaceContext;
64
65typedef struct {
66 // Returns the number of faces (triangles/quads) on the mesh to be processed.
67 int (*m_getNumFaces)(const SMikkTSpaceContext * pContext);
68
69 // Returns the number of vertices on face number iFace
70 // iFace is a number in the range {0, 1, ..., getNumFaces()-1}
71 int (*m_getNumVerticesOfFace)(const SMikkTSpaceContext * pContext, const int iFace);
72
73 // returns the position/normal/texcoord of the referenced face of vertex number iVert.
74 // iVert is in the range {0,1,2} for triangles and {0,1,2,3} for quads.
75 void (*m_getPosition)(const SMikkTSpaceContext * pContext, float fvPosOut[], const int iFace, const int iVert);
76 void (*m_getNormal)(const SMikkTSpaceContext * pContext, float fvNormOut[], const int iFace, const int iVert);
77 void (*m_getTexCoord)(const SMikkTSpaceContext * pContext, float fvTexcOut[], const int iFace, const int iVert);
78
79 // either (or both) of the two setTSpace callbacks can be set.
80 // The call-back m_setTSpaceBasic() is sufficient for basic normal mapping.
81
82 // This function is used to return the tangent and fSign to the application.
83 // fvTangent is a unit length vector.
84 // For normal maps it is sufficient to use the following simplified version of the bitangent which is generated at pixel/vertex level.
85 // bitangent = fSign * cross(vN, tangent);
86 // Note that the results are returned unindexed. It is possible to generate a new index list
87 // But averaging/overwriting tangent spaces by using an already existing index list WILL produce INCRORRECT results.
88 // DO NOT! use an already existing index list.
89 void (*m_setTSpaceBasic)(const SMikkTSpaceContext * pContext, const float fvTangent[], const float fSign, const int iFace, const int iVert);
90
91 // This function is used to return tangent space results to the application.
92 // fvTangent and fvBiTangent are unit length vectors and fMagS and fMagT are their
93 // true magnitudes which can be used for relief mapping effects.
94 // fvBiTangent is the "real" bitangent and thus may not be perpendicular to fvTangent.
95 // However, both are perpendicular to the vertex normal.
96 // For normal maps it is sufficient to use the following simplified version of the bitangent which is generated at pixel/vertex level.
97 // fSign = bIsOrientationPreserving ? 1.0f : (-1.0f);
98 // bitangent = fSign * cross(vN, tangent);
99 // Note that the results are returned unindexed. It is possible to generate a new index list
100 // But averaging/overwriting tangent spaces by using an already existing index list WILL produce INCRORRECT results.
101 // DO NOT! use an already existing index list.
102 void (*m_setTSpace)(const SMikkTSpaceContext * pContext, const float fvTangent[], const float fvBiTangent[], const float fMagS, const float fMagT,
103 const tbool bIsOrientationPreserving, const int iFace, const int iVert);
104} SMikkTSpaceInterface;
105
106struct SMikkTSpaceContext
107{
108 SMikkTSpaceInterface * m_pInterface; // initialized with callback functions
109 void * m_pUserData; // pointer to client side mesh data etc. (passed as the first parameter with every interface call)
110};
111
112// these are both thread safe!
113tbool genTangSpaceDefault(const SMikkTSpaceContext * pContext); // Default (recommended) fAngularThreshold is 180 degrees (which means threshold disabled)
114tbool genTangSpace(const SMikkTSpaceContext * pContext, const float fAngularThreshold);
115
116
117// To avoid visual errors (distortions/unwanted hard edges in lighting), when using sampled normal maps, the
118// normal map sampler must use the exact inverse of the pixel shader transformation.
119// The most efficient transformation we can possibly do in the pixel shader is
120// achieved by using, directly, the "unnormalized" interpolated tangent, bitangent and vertex normal: vT, vB and vN.
121// pixel shader (fast transform out)
122// vNout = normalize( vNt.x * vT + vNt.y * vB + vNt.z * vN );
123// where vNt is the tangent space normal. The normal map sampler must likewise use the
124// interpolated and "unnormalized" tangent, bitangent and vertex normal to be compliant with the pixel shader.
125// sampler does (exact inverse of pixel shader):
126// float3 row0 = cross(vB, vN);
127// float3 row1 = cross(vN, vT);
128// float3 row2 = cross(vT, vB);
129// float fSign = dot(vT, row0)<0 ? -1 : 1;
130// vNt = normalize( fSign * float3(dot(vNout,row0), dot(vNout,row1), dot(vNout,row2)) );
131// where vNout is the sampled normal in some chosen 3D space.
132//
133// Should you choose to reconstruct the bitangent in the pixel shader instead
134// of the vertex shader, as explained earlier, then be sure to do this in the normal map sampler also.
135// Finally, beware of quad triangulations. If the normal map sampler doesn't use the same triangulation of
136// quads as your renderer then problems will occur since the interpolated tangent spaces will differ
137// eventhough the vertex level tangent spaces match. This can be solved either by triangulating before
138// sampling/exporting or by using the order-independent choice of diagonal for splitting quads suggested earlier.
139// However, this must be used both by the sampler and your tools/rendering pipeline.
140
141#ifdef __cplusplus
142}
143#endif
144
145#endif
generated by cgit v1.2.3 (git 2.25.1) at 2025-06-29 14:24:05 +0000