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