blender/intern/mikktspace/mikktspace.c

/* SPDX-License-Identifier: Zlib
 * Copyright 2011 by Morten S. Mikkelsen. */

/** \file
 * \ingroup mikktspace
 */

#include <assert.h>
#include <float.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "mikktspace.h"

#define TFALSE 0
#define TTRUE 1

#ifndef M_PI
#  define M_PI 3.1415926535897932384626433832795
#endif

#define INTERNAL_RND_SORT_SEED 39871946

#ifdef _MSC_VER
#  define MIKK_INLINE static __forceinline
#else
#  define MIKK_INLINE static inline __attribute__((always_inline)) __attribute__((unused))
#endif

// internal structure
typedef struct {
  float x, y, z;
} SVec3;

MIKK_INLINE tbool veq(const SVec3 v1, const SVec3 v2)
{
  return (v1.x == v2.x) && (v1.y == v2.y) && (v1.z == v2.z);
}

MIKK_INLINE SVec3 vadd(const SVec3 v1, const SVec3 v2)
{
  SVec3 vRes;

  vRes.x = v1.x + v2.x;
  vRes.y = v1.y + v2.y;
  vRes.z = v1.z + v2.z;

  return vRes;
}

MIKK_INLINE SVec3 vsub(const SVec3 v1, const SVec3 v2)
{
  SVec3 vRes;

  vRes.x = v1.x - v2.x;
  vRes.y = v1.y - v2.y;
  vRes.z = v1.z - v2.z;

  return vRes;
}

MIKK_INLINE SVec3 vscale(const float fS, const SVec3 v)
{
  SVec3 vRes;

  vRes.x = fS * v.x;
  vRes.y = fS * v.y;
  vRes.z = fS * v.z;

  return vRes;
}

MIKK_INLINE float LengthSquared(const SVec3 v)
{
  return v.x * v.x + v.y * v.y + v.z * v.z;
}

MIKK_INLINE float Length(const SVec3 v)
{
  return sqrtf(LengthSquared(v));
}

#if 0  // UNUSED
MIKK_INLINE SVec3 Normalize(const SVec3 v)
{
  return vscale(1.0f / Length(v), v);
}
#endif

MIKK_INLINE SVec3 NormalizeSafe(const SVec3 v)
{
  const float len = Length(v);
  if (len != 0.0f) {
    return vscale(1.0f / len, v);
  }
  else {
    return v;
  }
}

MIKK_INLINE float vdot(const SVec3 v1, const SVec3 v2)
{
  return v1.x * v2.x + v1.y * v2.y + v1.z * v2.z;
}

MIKK_INLINE tbool NotZero(const float fX)
{
  // could possibly use FLT_EPSILON instead
  return fabsf(fX) > FLT_MIN;
}

#if 0  // UNUSED
MIKK_INLINE tbool VNotZero(const SVec3 v)
{
  // might change this to an epsilon based test
  return NotZero(v.x) || NotZero(v.y) || NotZero(v.z);
}
#endif

// Shift operations in C are only defined for shift values which are
// not negative and smaller than sizeof(value) * CHAR_BIT.
// The mask, used with bitwise-and (&), prevents undefined behavior
// when the shift count is 0 or >= the width of unsigned int.
MIKK_INLINE unsigned int rotl(unsigned int value, unsigned int count)
{
  const unsigned int mask = CHAR_BIT * sizeof(value) - 1;
  count &= mask;
  return (value << count) | (value >> (-count & mask));
}

typedef struct {
  int iNrFaces;
  int *pTriMembers;
} SSubGroup;

typedef struct {
  int iNrFaces;
  int *pFaceIndices;
  int iVertexRepresentitive;
  tbool bOrientPreservering;
} SGroup;

//
#define MARK_DEGENERATE 1
#define QUAD_ONE_DEGEN_TRI 2
#define GROUP_WITH_ANY 4
#define ORIENT_PRESERVING 8

typedef struct {
  int FaceNeighbors[3];
  SGroup *AssignedGroup[3];

  // normalized first order face derivatives
  SVec3 vOs, vOt;
  float fMagS, fMagT;  // original magnitudes

  // determines if the current and the next triangle are a quad.
  int iOrgFaceNumber;
  int iFlag, iTSpacesOffs;
  unsigned char vert_num[4];
} STriInfo;

typedef struct {
  SVec3 vOs;
  float fMagS;
  SVec3 vOt;
  float fMagT;
  int iCounter;  // this is to average back into quads.
  tbool bOrient;
} STSpace;

static int GenerateInitialVerticesIndexList(STriInfo pTriInfos[],
                                            int piTriList_out[],
                                            const SMikkTSpaceContext *pContext,
                                            const int iNrTrianglesIn);
static void GenerateSharedVerticesIndexList(int piTriList_in_and_out[],
                                            const SMikkTSpaceContext *pContext,
                                            const int iNrTrianglesIn);
static void InitTriInfo(STriInfo pTriInfos[],
                        const int piTriListIn[],
                        const SMikkTSpaceContext *pContext,
                        const int iNrTrianglesIn);
static int Build4RuleGroups(STriInfo pTriInfos[],
                            SGroup pGroups[],
                            int piGroupTrianglesBuffer[],
                            const int piTriListIn[],
                            const int iNrTrianglesIn);
static tbool GenerateTSpaces(STSpace psTspace[],
                             const STriInfo pTriInfos[],
                             const SGroup pGroups[],
                             const int iNrActiveGroups,
                             const int piTriListIn[],
                             const float fThresCos,
                             const SMikkTSpaceContext *pContext);

MIKK_INLINE int MakeIndex(const int iFace, const int iVert)
{
  assert(iVert >= 0 && iVert < 4 && iFace >= 0);
  return (iFace << 2) | (iVert & 0x3);
}

MIKK_INLINE void IndexToData(int *piFace, int *piVert, const int iIndexIn)
{
  piVert[0] = iIndexIn & 0x3;
  piFace[0] = iIndexIn >> 2;
}

static STSpace AvgTSpace(const STSpace *pTS0, const STSpace *pTS1)
{
  STSpace ts_res;

  // this if is important. Due to floating point precision
  // averaging when ts0==ts1 will cause a slight difference
  // which results in tangent space splits later on
  if (pTS0->fMagS == pTS1->fMagS && pTS0->fMagT == pTS1->fMagT && veq(pTS0->vOs, pTS1->vOs) &&
      veq(pTS0->vOt, pTS1->vOt)) {
    ts_res.fMagS = pTS0->fMagS;
    ts_res.fMagT = pTS0->fMagT;
    ts_res.vOs = pTS0->vOs;
    ts_res.vOt = pTS0->vOt;
  }
  else {
    ts_res.fMagS = 0.5f * (pTS0->fMagS + pTS1->fMagS);
    ts_res.fMagT = 0.5f * (pTS0->fMagT + pTS1->fMagT);
    ts_res.vOs = vadd(pTS0->vOs, pTS1->vOs);
    ts_res.vOt = vadd(pTS0->vOt, pTS1->vOt);
    ts_res.vOs = NormalizeSafe(ts_res.vOs);
    ts_res.vOt = NormalizeSafe(ts_res.vOt);
  }

  return ts_res;
}

MIKK_INLINE SVec3 GetPosition(const SMikkTSpaceContext *pContext, const int index);
MIKK_INLINE SVec3 GetNormal(const SMikkTSpaceContext *pContext, const int index);
MIKK_INLINE SVec3 GetTexCoord(const SMikkTSpaceContext *pContext, const int index);

// degen triangles
static void DegenPrologue(STriInfo pTriInfos[],
                          int piTriList_out[],
                          const int iNrTrianglesIn,
                          const int iTotTris);
static void DegenEpilogue(STSpace psTspace[],
                          STriInfo pTriInfos[],
                          int piTriListIn[],
                          const SMikkTSpaceContext *pContext,
                          const int iNrTrianglesIn,
                          const int iTotTris);

tbool genTangSpaceDefault(const SMikkTSpaceContext *pContext)
{
  return genTangSpace(pContext, 180.0f);
}

tbool genTangSpace(const SMikkTSpaceContext *pContext, const float fAngularThreshold)
{
  // count nr_triangles
  int *piTriListIn = NULL, *piGroupTrianglesBuffer = NULL;
  STriInfo *pTriInfos = NULL;
  SGroup *pGroups = NULL;
  STSpace *psTspace = NULL;
  int iNrTrianglesIn = 0, f = 0, t = 0, i = 0;
  int iNrTSPaces = 0, iTotTris = 0, iDegenTriangles = 0, iNrMaxGroups = 0;
  int iNrActiveGroups = 0, index = 0;
  const int iNrFaces = pContext->m_pInterface->m_getNumFaces(pContext);
  tbool bRes = TFALSE;
  const float fThresCos = cosf((fAngularThreshold * (float)M_PI) / 180.0f);

  // verify all call-backs have been set
  if (pContext->m_pInterface->m_getNumFaces == NULL ||
      pContext->m_pInterface->m_getNumVerticesOfFace == NULL ||
      pContext->m_pInterface->m_getPosition == NULL ||
      pContext->m_pInterface->m_getNormal == NULL || pContext->m_pInterface->m_getTexCoord == NULL)
    return TFALSE;

  // count triangles on supported faces
  for (f = 0; f < iNrFaces; f++) {
    const int verts = pContext->m_pInterface->m_getNumVerticesOfFace(pContext, f);
    if (verts == 3)
      ++iNrTrianglesIn;
    else if (verts == 4)
      iNrTrianglesIn += 2;
  }
  if (iNrTrianglesIn <= 0)
    return TFALSE;

  // allocate memory for an index list
  piTriListIn = (int *)malloc(sizeof(int[3]) * iNrTrianglesIn);
  pTriInfos = (STriInfo *)malloc(sizeof(STriInfo) * iNrTrianglesIn);
  if (piTriListIn == NULL || pTriInfos == NULL) {
    if (piTriListIn != NULL)
      free(piTriListIn);
    if (pTriInfos != NULL)
      free(pTriInfos);
    return TFALSE;
  }

  // make an initial triangle --> face index list
  iNrTSPaces = GenerateInitialVerticesIndexList(pTriInfos, piTriListIn, pContext, iNrTrianglesIn);

  // make a welded index list of identical positions and attributes (pos, norm, texc)
  // printf("gen welded index list begin\n");
  GenerateSharedVerticesIndexList(piTriListIn, pContext, iNrTrianglesIn);
  // printf("gen welded index list end\n");

  // Mark all degenerate triangles
  iTotTris = iNrTrianglesIn;
  iDegenTriangles = 0;
  for (t = 0; t < iTotTris; t++) {
    const int i0 = piTriListIn[t * 3 + 0];
    const int i1 = piTriListIn[t * 3 + 1];
    const int i2 = piTriListIn[t * 3 + 2];
    const SVec3 p0 = GetPosition(pContext, i0);
    const SVec3 p1 = GetPosition(pContext, i1);
    const SVec3 p2 = GetPosition(pContext, i2);
    if (veq(p0, p1) || veq(p0, p2) || veq(p1, p2))  // degenerate
    {
      pTriInfos[t].iFlag |= MARK_DEGENERATE;
      ++iDegenTriangles;
    }
  }
  iNrTrianglesIn = iTotTris - iDegenTriangles;

  // mark all triangle pairs that belong to a quad with only one
  // good triangle. These need special treatment in DegenEpilogue().
  // Additionally, move all good triangles to the start of
  // pTriInfos[] and piTriListIn[] without changing order and
  // put the degenerate triangles last.
  DegenPrologue(pTriInfos, piTriListIn, iNrTrianglesIn, iTotTris);

  // evaluate triangle level attributes and neighbor list
  // printf("gen neighbors list begin\n");
  InitTriInfo(pTriInfos, piTriListIn, pContext, iNrTrianglesIn);
  // printf("gen neighbors list end\n");

  // based on the 4 rules, identify groups based on connectivity
  iNrMaxGroups = iNrTrianglesIn * 3;
  pGroups = (SGroup *)malloc(sizeof(SGroup) * iNrMaxGroups);
  piGroupTrianglesBuffer = (int *)malloc(sizeof(int[3]) * iNrTrianglesIn);
  if (pGroups == NULL || piGroupTrianglesBuffer == NULL) {
    if (pGroups != NULL)
      free(pGroups);
    if (piGroupTrianglesBuffer != NULL)
      free(piGroupTrianglesBuffer);
    free(piTriListIn);
    free(pTriInfos);
    return TFALSE;
  }
  // printf("gen 4rule groups begin\n");
  iNrActiveGroups = Build4RuleGroups(
      pTriInfos, pGroups, piGroupTrianglesBuffer, piTriListIn, iNrTrianglesIn);
  // printf("gen 4rule groups end\n");

  //

  psTspace = (STSpace *)malloc(sizeof(STSpace) * iNrTSPaces);
  if (psTspace == NULL) {
    free(piTriListIn);
    free(pTriInfos);
    free(pGroups);
    free(piGroupTrianglesBuffer);
    return TFALSE;
  }
  memset(psTspace, 0, sizeof(STSpace) * iNrTSPaces);
  for (t = 0; t < iNrTSPaces; t++) {
    psTspace[t].vOs.x = 1.0f;
    psTspace[t].vOs.y = 0.0f;
    psTspace[t].vOs.z = 0.0f;
    psTspace[t].fMagS = 1.0f;
    psTspace[t].vOt.x = 0.0f;
    psTspace[t].vOt.y = 1.0f;
    psTspace[t].vOt.z = 0.0f;
    psTspace[t].fMagT = 1.0f;
  }

  // make tspaces, each group is split up into subgroups if necessary
  // based on fAngularThreshold. Finally a tangent space is made for
  // every resulting subgroup
  // printf("gen tspaces begin\n");
  bRes = GenerateTSpaces(
      psTspace, pTriInfos, pGroups, iNrActiveGroups, piTriListIn, fThresCos, pContext);
  // printf("gen tspaces end\n");

  // clean up
  free(pGroups);
  free(piGroupTrianglesBuffer);

  if (!bRes)  // if an allocation in GenerateTSpaces() failed
  {
    // clean up and return false
    free(pTriInfos);
    free(piTriListIn);
    free(psTspace);
    return TFALSE;
  }

  // degenerate quads with one good triangle will be fixed by copying a space from
  // the good triangle to the coinciding vertex.
  // all other degenerate triangles will just copy a space from any good triangle
  // with the same welded index in piTriListIn[].
  DegenEpilogue(psTspace, pTriInfos, piTriListIn, pContext, iNrTrianglesIn, iTotTris);

  free(pTriInfos);
  free(piTriListIn);

  index = 0;
  for (f = 0; f < iNrFaces; f++) {
    const int verts = pContext->m_pInterface->m_getNumVerticesOfFace(pContext, f);
    if (verts != 3 && verts != 4) {
      continue;
    }

    // I've decided to let degenerate triangles and group-with-anythings
    // vary between left/right hand coordinate systems at the vertices.
    // All healthy triangles on the other hand are built to always be either or.
#if 0
    // force the coordinate system orientation to be uniform for every face.
    // (this is already the case for good triangles but not for
    // degenerate ones and those with bGroupWithAnything==true)
    bool bOrient = psTspace[index].bOrient;
    if (psTspace[index].iCounter == 0)  // tspace was not derived from a group
    {
      // look for a space created in GenerateTSpaces() by iCounter>0
      bool bNotFound = true;
      int i=1;
      while (i<verts && bNotFound)
      {
        if (psTspace[index+i].iCounter > 0) bNotFound=false;
        else ++i;
      }
      if (!bNotFound) bOrient = psTspace[index+i].bOrient;
    }
#endif

    // set data
    for (i = 0; i < verts; i++) {
      const STSpace *pTSpace = &psTspace[index];
      float tang[] = {pTSpace->vOs.x, pTSpace->vOs.y, pTSpace->vOs.z};
      float bitang[] = {pTSpace->vOt.x, pTSpace->vOt.y, pTSpace->vOt.z};
      if (pContext->m_pInterface->m_setTSpace != NULL)
        pContext->m_pInterface->m_setTSpace(
            pContext, tang, bitang, pTSpace->fMagS, pTSpace->fMagT, pTSpace->bOrient, f, i);
      if (pContext->m_pInterface->m_setTSpaceBasic != NULL)
        pContext->m_pInterface->m_setTSpaceBasic(
            pContext, tang, pTSpace->bOrient == TTRUE ? 1.0f : (-1.0f), f, i);

      ++index;
    }
  }

  free(psTspace);

  return TTRUE;
}

///////////////////////////////////////////////////////////////////////////////////////////////////

static void GenerateSharedVerticesIndexListSlow(int piTriList_in_and_out[],
                                                const SMikkTSpaceContext *pContext,
                                                const int iNrTrianglesIn);

typedef unsigned int uint;

static uint float_as_uint(const float v)
{
  return *((uint *)(&v));
}

#define HASH(x, y, z) (((x)*73856093) ^ ((y)*19349663) ^ ((z)*83492791))
#define HASH_F(x, y, z) HASH(float_as_uint(x), float_as_uint(y), float_as_uint(z))

/* Sort comp and data based on comp.
 * comp2 and data2 are used as temporary storage. */
static void radixsort_pair(uint *comp, int *data, uint *comp2, int *data2, int n)
{
  int shift = 0;
  for (int pass = 0; pass < 4; pass++, shift += 8) {
    int bins[257] = {0};
    /* Count number of elements per bin. */
    for (int i = 0; i < n; i++) {
      bins[((comp[i] >> shift) & 0xff) + 1]++;
    }
    /* Compute prefix sum to find position of each bin in the sorted array. */
    for (int i = 2; i < 256; i++) {
      bins[i] += bins[i - 1];
    }
    /* Insert the elements in their correct location based on their bin. */
    for (int i = 0; i < n; i++) {
      int pos = bins[(comp[i] >> shift) & 0xff]++;
      comp2[pos] = comp[i];
      data2[pos] = data[i];
    }

    /* Swap arrays. */
    int *tmpdata = data;
    data = data2;
    data2 = tmpdata;
    uint *tmpcomp = comp;
    comp = comp2;
    comp2 = tmpcomp;
  }
}

/* Merge identical vertices.
 * To find vertices with identical position, normal and texcoord, we calculate a hash of the 9
 * values. Then, by sorting based on that hash, identical elements (having identical hashes) will
 * be moved next to each other. Since there might be hash collisions, the elements of each block
 * are then compared with each other and duplicates are merged.
 */
static void GenerateSharedVerticesIndexList(int piTriList_in_and_out[],
                                            const SMikkTSpaceContext *pContext,
                                            const int iNrTrianglesIn)
{
  int numVertices = iNrTrianglesIn * 3;

  uint *hashes = (uint *)malloc(sizeof(uint) * numVertices);
  int *indices = (int *)malloc(sizeof(int) * numVertices);
  uint *temp_hashes = (uint *)malloc(sizeof(uint) * numVertices);
  int *temp_indices = (int *)malloc(sizeof(int) * numVertices);

  if (hashes == NULL || indices == NULL || temp_hashes == NULL || temp_indices == NULL) {
    free(hashes);
    free(indices);
    free(temp_hashes);
    free(temp_indices);

    GenerateSharedVerticesIndexListSlow(piTriList_in_and_out, pContext, iNrTrianglesIn);
    return;
  }

  for (int i = 0; i < numVertices; i++) {
    const int index = piTriList_in_and_out[i];

    const SVec3 vP = GetPosition(pContext, index);
    const uint hashP = HASH_F(vP.x, vP.y, vP.z);

    const SVec3 vN = GetNormal(pContext, index);
    const uint hashN = HASH_F(vN.x, vN.y, vN.z);

    const SVec3 vT = GetTexCoord(pContext, index);
    const uint hashT = HASH_F(vT.x, vT.y, vT.z);

    hashes[i] = HASH(hashP, hashN, hashT);
    indices[i] = i;
  }

  radixsort_pair(hashes, indices, temp_hashes, temp_indices, numVertices);

  free(temp_hashes);
  free(temp_indices);

  /* Process blocks of vertices with the same hash.
   * Vertices in the block might still be separate, but we know for sure that
   * vertices in different blocks will never be identical. */
  int blockstart = 0;
  while (blockstart < numVertices) {
    /* Find end of this block (exclusive). */
    uint hash = hashes[blockstart];
    int blockend = blockstart + 1;
    for (; blockend < numVertices; blockend++) {
      if (hashes[blockend] != hash)
        break;
    }

    /* If there's only one vertex with this hash, we don't have anything to compare. */
    if (blockend > blockstart + 1) {
      for (int i = blockstart; i < blockend; i++) {
        int index1 = piTriList_in_and_out[indices[i]];
        const SVec3 vP = GetPosition(pContext, index1);
        const SVec3 vN = GetNormal(pContext, index1);
        const SVec3 vT = GetTexCoord(pContext, index1);
        for (int i2 = i + 1; i2 < blockend; i2++) {
          int index2 = piTriList_in_and_out[indices[i2]];
          if (index1 == index2)
            continue;

          if (veq(vP, GetPosition(pContext, index2)) && veq(vN, GetNormal(pContext, index2)) &&
              veq(vT, GetTexCoord(pContext, index2))) {
            piTriList_in_and_out[indices[i2]] = index1;
            /* Once i2>i has been identified as a duplicate, we can stop since any
             * i3>i2>i that is a duplicate of i (and therefore also i2) will also be
             * compared to i2 and therefore be identified there anyways. */
            break;
          }
        }
      }
    }

    /* Advance to next block. */
    blockstart = blockend;
  }

  free(hashes);
  free(indices);
}

static void GenerateSharedVerticesIndexListSlow(int piTriList_in_and_out[],
                                                const SMikkTSpaceContext *pContext,
                                                const int iNrTrianglesIn)
{
  int iNumUniqueVerts = 0, t = 0, i = 0;
  for (t = 0; t < iNrTrianglesIn; t++) {
    for (i = 0; i < 3; i++) {
      const int offs = t * 3 + i;
      const int index = piTriList_in_and_out[offs];

      const SVec3 vP = GetPosition(pContext, index);
      const SVec3 vN = GetNormal(pContext, index);
      const SVec3 vT = GetTexCoord(pContext, index);

      tbool bFound = TFALSE;
      int t2 = 0, index2rec = -1;
      while (!bFound && t2 <= t) {
        int j = 0;
        while (!bFound && j < 3) {
          const int index2 = piTriList_in_and_out[t2 * 3 + j];
          const SVec3 vP2 = GetPosition(pContext, index2);
          const SVec3 vN2 = GetNormal(pContext, index2);
          const SVec3 vT2 = GetTexCoord(pContext, index2);

          if (veq(vP, vP2) && veq(vN, vN2) && veq(vT, vT2))
            bFound = TTRUE;
          else
            ++j;
        }
        if (!bFound)
          ++t2;
      }

      assert(bFound);
      // if we found our own
      if (index2rec == index) {
        ++iNumUniqueVerts;
      }

      piTriList_in_and_out[offs] = index2rec;
    }
  }
}

static int GenerateInitialVerticesIndexList(STriInfo pTriInfos[],
                                            int piTriList_out[],
                                            const SMikkTSpaceContext *pContext,
                                            const int iNrTrianglesIn)
{
  int iTSpacesOffs = 0, f = 0, t = 0;
  int iDstTriIndex = 0;
  const int iNrFaces = pContext->m_pInterface->m_getNumFaces(pContext);
  for (f = 0; f < iNrFaces; f++) {
    const int verts = pContext->m_pInterface->m_getNumVerticesOfFace(pContext, f);
    if (verts != 3 && verts != 4)
      continue;

    pTriInfos[iDstTriIndex].iOrgFaceNumber = f;
    pTriInfos[iDstTriIndex].iTSpacesOffs = iTSpacesOffs;

    if (verts == 3) {
      unsigned char *pVerts = pTriInfos[iDstTriIndex].vert_num;
      pVerts[0] = 0;
      pVerts[1] = 1;
      pVerts[2] = 2;
      piTriList_out[iDstTriIndex * 3 + 0] = MakeIndex(f, 0);
      piTriList_out[iDstTriIndex * 3 + 1] = MakeIndex(f, 1);
      piTriList_out[iDstTriIndex * 3 + 2] = MakeIndex(f, 2);
      ++iDstTriIndex;  // next
    }
    else {
      {
        pTriInfos[iDstTriIndex + 1].iOrgFaceNumber = f;
        pTriInfos[iDstTriIndex + 1].iTSpacesOffs = iTSpacesOffs;
      }

      {
        // need an order independent way to evaluate
        // tspace on quads. This is done by splitting
        // along the shortest diagonal.
        const int i0 = MakeIndex(f, 0);
        const int i1 = MakeIndex(f, 1);
        const int i2 = MakeIndex(f, 2);
        const int i3 = MakeIndex(f, 3);
        const SVec3 T0 = GetTexCoord(pContext, i0);
        const SVec3 T1 = GetTexCoord(pContext, i1);
        const SVec3 T2 = GetTexCoord(pContext, i2);
        const SVec3 T3 = GetTexCoord(pContext, i3);
        const float distSQ_02 = LengthSquared(vsub(T2, T0));
        const float distSQ_13 = LengthSquared(vsub(T3, T1));
        tbool bQuadDiagIs_02;
        if (distSQ_02 < distSQ_13)
          bQuadDiagIs_02 = TTRUE;
        else if (distSQ_13 < distSQ_02)
          bQuadDiagIs_02 = TFALSE;
        else {
          const SVec3 P0 = GetPosition(pContext, i0);
          const SVec3 P1 = GetPosition(pContext, i1);
          const SVec3 P2 = GetPosition(pContext, i2);
          const SVec3 P3 = GetPosition(pContext, i3);
          const float distSQ_02 = LengthSquared(vsub(P2, P0));
          const float distSQ_13 = LengthSquared(vsub(P3, P1));

          bQuadDiagIs_02 = distSQ_13 < distSQ_02 ? TFALSE : TTRUE;
        }

        if (bQuadDiagIs_02) {
          {
            unsigned char *pVerts_A = pTriInfos[iDstTriIndex].vert_num;
            pVerts_A[0] = 0;
            pVerts_A[1] = 1;
            pVerts_A[2] = 2;
          }
          piTriList_out[iDstTriIndex * 3 + 0] = i0;
          piTriList_out[iDstTriIndex * 3 + 1] = i1;
          piTriList_out[iDstTriIndex * 3 + 2] = i2;
          ++iDstTriIndex;  // next
          {
            unsigned char *pVerts_B = pTriInfos[iDstTriIndex].vert_num;
            pVerts_B[0] = 0;
            pVerts_B[1] = 2;
            pVerts_B[2] = 3;
          }
          piTriList_out[iDstTriIndex * 3 + 0] = i0;
          piTriList_out[iDstTriIndex * 3 + 1] = i2;
          piTriList_out[iDstTriIndex * 3 + 2] = i3;
          ++iDstTriIndex;  // next
        }
        else {
          {
            unsigned char *pVerts_A = pTriInfos[iDstTriIndex].vert_num;
            pVerts_A[0] = 0;
            pVerts_A[1] = 1;
            pVerts_A[2] = 3;
          }
          piTriList_out[iDstTriIndex * 3 + 0] = i0;
          piTriList_out[iDstTriIndex * 3 + 1] = i1;
          piTriList_out[iDstTriIndex * 3 + 2] = i3;
          ++iDstTriIndex;  // next
          {
            unsigned char *pVerts_B = pTriInfos[iDstTriIndex].vert_num;
            pVerts_B[0] = 1;
            pVerts_B[1] = 2;
            pVerts_B[2] = 3;
          }
          piTriList_out[iDstTriIndex * 3 + 0] = i1;
          piTriList_out[iDstTriIndex * 3 + 1] = i2;
          piTriList_out[iDstTriIndex * 3 + 2] = i3;
          ++iDstTriIndex;  // next
        }
      }
    }

    iTSpacesOffs += verts;
    assert(iDstTriIndex <= iNrTrianglesIn);
  }

  for (t = 0; t < iNrTrianglesIn; t++)
    pTriInfos[t].iFlag = 0;

  // return total amount of tspaces
  return iTSpacesOffs;
}

MIKK_INLINE SVec3 GetPosition(const SMikkTSpaceContext *pContext, const int index)
{
  int iF, iI;
  SVec3 res;
  float pos[3];
  IndexToData(&iF, &iI, index);
  pContext->m_pInterface->m_getPosition(pContext, pos, iF, iI);
  res.x = pos[0];
  res.y = pos[1];
  res.z = pos[2];
  return res;
}

MIKK_INLINE SVec3 GetNormal(const SMikkTSpaceContext *pContext, const int index)
{
  int iF, iI;
  SVec3 res;
  float norm[3];
  IndexToData(&iF, &iI, index);
  pContext->m_pInterface->m_getNormal(pContext, norm, iF, iI);
  res.x = norm[0];
  res.y = norm[1];
  res.z = norm[2];
  return res;
}

MIKK_INLINE SVec3 GetTexCoord(const SMikkTSpaceContext *pContext, const int index)
{
  int iF, iI;
  SVec3 res;
  float texc[2];
  IndexToData(&iF, &iI, index);
  pContext->m_pInterface->m_getTexCoord(pContext, texc, iF, iI);
  res.x = texc[0];
  res.y = texc[1];
  res.z = 1.0f;
  return res;
}

///////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////

typedef union {
  struct {
    int i0, i1, f;
  };
  int array[3];
} SEdge;

static void BuildNeighborsFast(STriInfo pTriInfos[],
                               SEdge *pEdges,
                               const int piTriListIn[],
                               const int iNrTrianglesIn);
static void BuildNeighborsSlow(STriInfo pTriInfos[],
                               const int piTriListIn[],
                               const int iNrTrianglesIn);

// returns the texture area times 2
static float CalcTexArea(const SMikkTSpaceContext *pContext, const int indices[])
{
  const SVec3 t1 = GetTexCoord(pContext, indices[0]);
  const SVec3 t2 = GetTexCoord(pContext, indices[1]);
  const SVec3 t3 = GetTexCoord(pContext, indices[2]);

  const float t21x = t2.x - t1.x;
  const float t21y = t2.y - t1.y;
  const float t31x = t3.x - t1.x;
  const float t31y = t3.y - t1.y;

  const float fSignedAreaSTx2 = t21x * t31y - t21y * t31x;

  return fSignedAreaSTx2 < 0 ? (-fSignedAreaSTx2) : fSignedAreaSTx2;
}

static void InitTriInfo(STriInfo pTriInfos[],
                        const int piTriListIn[],
                        const SMikkTSpaceContext *pContext,
                        const int iNrTrianglesIn)
{
  int f = 0, i = 0, t = 0;
  // pTriInfos[f].iFlag is cleared in GenerateInitialVerticesIndexList()
  // which is called before this function.

  // generate neighbor info list
  for (f = 0; f < iNrTrianglesIn; f++)
    for (i = 0; i < 3; i++) {
      pTriInfos[f].FaceNeighbors[i] = -1;
      pTriInfos[f].AssignedGroup[i] = NULL;

      pTriInfos[f].vOs.x = 0.0f;
      pTriInfos[f].vOs.y = 0.0f;
      pTriInfos[f].vOs.z = 0.0f;
      pTriInfos[f].vOt.x = 0.0f;
      pTriInfos[f].vOt.y = 0.0f;
      pTriInfos[f].vOt.z = 0.0f;
      pTriInfos[f].fMagS = 0;
      pTriInfos[f].fMagT = 0;

      // assumed bad
      pTriInfos[f].iFlag |= GROUP_WITH_ANY;
    }

  // evaluate first order derivatives
  for (f = 0; f < iNrTrianglesIn; f++) {
    // initial values
    const SVec3 v1 = GetPosition(pContext, piTriListIn[f * 3 + 0]);
    const SVec3 v2 = GetPosition(pContext, piTriListIn[f * 3 + 1]);
    const SVec3 v3 = GetPosition(pContext, piTriListIn[f * 3 + 2]);
    const SVec3 t1 = GetTexCoord(pContext, piTriListIn[f * 3 + 0]);
    const SVec3 t2 = GetTexCoord(pContext, piTriListIn[f * 3 + 1]);
    const SVec3 t3 = GetTexCoord(pContext, piTriListIn[f * 3 + 2]);

    const float t21x = t2.x - t1.x;
    const float t21y = t2.y - t1.y;
    const float t31x = t3.x - t1.x;
    const float t31y = t3.y - t1.y;
    const SVec3 d1 = vsub(v2, v1);
    const SVec3 d2 = vsub(v3, v1);

    const float fSignedAreaSTx2 = t21x * t31y - t21y * t31x;
    // assert(fSignedAreaSTx2!=0);
    SVec3 vOs = vsub(vscale(t31y, d1), vscale(t21y, d2));   // eq 18
    SVec3 vOt = vadd(vscale(-t31x, d1), vscale(t21x, d2));  // eq 19

    pTriInfos[f].iFlag |= (fSignedAreaSTx2 > 0 ? ORIENT_PRESERVING : 0);

    if (NotZero(fSignedAreaSTx2)) {
      const float fAbsArea = fabsf(fSignedAreaSTx2);
      const float fLenOs = Length(vOs);
      const float fLenOt = Length(vOt);
      const float fS = (pTriInfos[f].iFlag & ORIENT_PRESERVING) == 0 ? (-1.0f) : 1.0f;
      if (NotZero(fLenOs))
        pTriInfos[f].vOs = vscale(fS / fLenOs, vOs);
      if (NotZero(fLenOt))
        pTriInfos[f].vOt = vscale(fS / fLenOt, vOt);

      // evaluate magnitudes prior to normalization of vOs and vOt
      pTriInfos[f].fMagS = fLenOs / fAbsArea;
      pTriInfos[f].fMagT = fLenOt / fAbsArea;

      // if this is a good triangle
      if (NotZero(pTriInfos[f].fMagS) && NotZero(pTriInfos[f].fMagT))
        pTriInfos[f].iFlag &= (~GROUP_WITH_ANY);
    }
  }

  // force otherwise healthy quads to a fixed orientation
  while (t < (iNrTrianglesIn - 1)) {
    const int iFO_a = pTriInfos[t].iOrgFaceNumber;
    const int iFO_b = pTriInfos[t + 1].iOrgFaceNumber;
    if (iFO_a == iFO_b)  // this is a quad
    {
      const tbool bIsDeg_a = (pTriInfos[t].iFlag & MARK_DEGENERATE) != 0 ? TTRUE : TFALSE;
      const tbool bIsDeg_b = (pTriInfos[t + 1].iFlag & MARK_DEGENERATE) != 0 ? TTRUE : TFALSE;

      // bad triangles should already have been removed by
      // DegenPrologue(), but just in case check bIsDeg_a and bIsDeg_a are false
      if ((bIsDeg_a || bIsDeg_b) == TFALSE) {
        const tbool bOrientA = (pTriInfos[t].iFlag & ORIENT_PRESERVING) != 0 ? TTRUE : TFALSE;
        const tbool bOrientB = (pTriInfos[t + 1].iFlag & ORIENT_PRESERVING) != 0 ? TTRUE : TFALSE;
        // if this happens the quad has extremely bad mapping!!
        if (bOrientA != bOrientB) {
          // printf("found quad with bad mapping\n");
          tbool bChooseOrientFirstTri = TFALSE;
          if ((pTriInfos[t + 1].iFlag & GROUP_WITH_ANY) != 0)
            bChooseOrientFirstTri = TTRUE;
          else if (CalcTexArea(pContext, &piTriListIn[t * 3 + 0]) >=
                   CalcTexArea(pContext, &piTriListIn[(t + 1) * 3 + 0]))
            bChooseOrientFirstTri = TTRUE;

          // force match
          {
            const int t0 = bChooseOrientFirstTri ? t : (t + 1);
            const int t1 = bChooseOrientFirstTri ? (t + 1) : t;
            pTriInfos[t1].iFlag &= (~ORIENT_PRESERVING);                       // clear first
            pTriInfos[t1].iFlag |= (pTriInfos[t0].iFlag & ORIENT_PRESERVING);  // copy bit
          }
        }
      }
      t += 2;
    }
    else
      ++t;
  }

  // match up edge pairs
  {
    SEdge *pEdges = (SEdge *)malloc(sizeof(SEdge[3]) * iNrTrianglesIn);
    if (pEdges == NULL)
      BuildNeighborsSlow(pTriInfos, piTriListIn, iNrTrianglesIn);
    else {
      BuildNeighborsFast(pTriInfos, pEdges, piTriListIn, iNrTrianglesIn);

      free(pEdges);
    }
  }
}

///////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////

static tbool AssignRecur(const int piTriListIn[],
                         STriInfo psTriInfos[],
                         const int iMyTriIndex,
                         SGroup *pGroup);
MIKK_INLINE void AddTriToGroup(SGroup *pGroup, const int iTriIndex);

static int Build4RuleGroups(STriInfo pTriInfos[],
                            SGroup pGroups[],
                            int piGroupTrianglesBuffer[],
                            const int piTriListIn[],
                            const int iNrTrianglesIn)
{
  const int iNrMaxGroups = iNrTrianglesIn * 3;
  int iNrActiveGroups = 0;
  int iOffset = 0, f = 0, i = 0;
  (void)iNrMaxGroups; /* quiet warnings in non debug mode */
  for (f = 0; f < iNrTrianglesIn; f++) {
    for (i = 0; i < 3; i++) {
      // if not assigned to a group
      if ((pTriInfos[f].iFlag & GROUP_WITH_ANY) == 0 && pTriInfos[f].AssignedGroup[i] == NULL) {
        tbool bOrPre;
        int neigh_indexL, neigh_indexR;
        const int vert_index = piTriListIn[f * 3 + i];
        assert(iNrActiveGroups < iNrMaxGroups);
        pTriInfos[f].AssignedGroup[i] = &pGroups[iNrActiveGroups];
        pTriInfos[f].AssignedGroup[i]->iVertexRepresentitive = vert_index;
        pTriInfos[f].AssignedGroup[i]->bOrientPreservering = (pTriInfos[f].iFlag &
                                                              ORIENT_PRESERVING) != 0;
        pTriInfos[f].AssignedGroup[i]->iNrFaces = 0;
        pTriInfos[f].AssignedGroup[i]->pFaceIndices = &piGroupTrianglesBuffer[iOffset];
        ++iNrActiveGroups;

        AddTriToGroup(pTriInfos[f].AssignedGroup[i], f);
        bOrPre = (pTriInfos[f].iFlag & ORIENT_PRESERVING) != 0 ? TTRUE : TFALSE;
        neigh_indexL = pTriInfos[f].FaceNeighbors[i];
        neigh_indexR = pTriInfos[f].FaceNeighbors[i > 0 ? (i - 1) : 2];
        if (neigh_indexL >= 0)  // neighbor
        {
          const tbool bAnswer = AssignRecur(
              piTriListIn, pTriInfos, neigh_indexL, pTriInfos[f].AssignedGroup[i]);

          const tbool bOrPre2 = (pTriInfos[neigh_indexL].iFlag & ORIENT_PRESERVING) != 0 ? TTRUE :
                                                                                           TFALSE;
          const tbool bDiff = bOrPre != bOrPre2 ? TTRUE : TFALSE;
          assert(bAnswer || bDiff);
          (void)bAnswer, (void)bDiff; /* quiet warnings in non debug mode */
        }
        if (neigh_indexR >= 0)  // neighbor
        {
          const tbool bAnswer = AssignRecur(
              piTriListIn, pTriInfos, neigh_indexR, pTriInfos[f].AssignedGroup[i]);

          const tbool bOrPre2 = (pTriInfos[neigh_indexR].iFlag & ORIENT_PRESERVING) != 0 ? TTRUE :
                                                                                           TFALSE;
          const tbool bDiff = bOrPre != bOrPre2 ? TTRUE : TFALSE;
          assert(bAnswer || bDiff);
          (void)bAnswer, (void)bDiff; /* quiet warnings in non debug mode */
        }

        // update offset
        iOffset += pTriInfos[f].AssignedGroup[i]->iNrFaces;
        // since the groups are disjoint a triangle can never
        // belong to more than 3 groups. Subsequently something
        // is completely screwed if this assertion ever hits.
        assert(iOffset <= iNrMaxGroups);
      }
    }
  }

  return iNrActiveGroups;
}

MIKK_INLINE void AddTriToGroup(SGroup *pGroup, const int iTriIndex)
{
  pGroup->pFaceIndices[pGroup->iNrFaces] = iTriIndex;
  ++pGroup->iNrFaces;
}

static tbool AssignRecur(const int piTriListIn[],
                         STriInfo psTriInfos[],
                         const int iMyTriIndex,
                         SGroup *pGroup)
{
  STriInfo *pMyTriInfo = &psTriInfos[iMyTriIndex];

  // track down vertex
  const int iVertRep = pGroup->iVertexRepresentitive;
  const int *pVerts = &piTriListIn[3 * iMyTriIndex + 0];
  int i = -1;
  if (pVerts[0] == iVertRep)
    i = 0;
  else if (pVerts[1] == iVertRep)
    i = 1;
  else if (pVerts[2] == iVertRep)
    i = 2;
  assert(i >= 0 && i < 3);

  // early out
  if (pMyTriInfo->AssignedGroup[i] == pGroup)
    return TTRUE;
  else if (pMyTriInfo->AssignedGroup[i] != NULL)
    return TFALSE;
  if ((pMyTriInfo->iFlag & GROUP_WITH_ANY) != 0) {
    // first to group with a group-with-anything triangle
    // determines its orientation.
    // This is the only existing order dependency in the code!!
    if (pMyTriInfo->AssignedGroup[0] == NULL && pMyTriInfo->AssignedGroup[1] == NULL &&
        pMyTriInfo->AssignedGroup[2] == NULL) {
      pMyTriInfo->iFlag &= (~ORIENT_PRESERVING);
      pMyTriInfo->iFlag |= (pGroup->bOrientPreservering ? ORIENT_PRESERVING : 0);
    }
  }
  {
    const tbool bOrient = (pMyTriInfo->iFlag & ORIENT_PRESERVING) != 0 ? TTRUE : TFALSE;
    if (bOrient != pGroup->bOrientPreservering)
      return TFALSE;
  }

  AddTriToGroup(pGroup, iMyTriIndex);
  pMyTriInfo->AssignedGroup[i] = pGroup;

  {
    const int neigh_indexL = pMyTriInfo->FaceNeighbors[i];
    const int neigh_indexR = pMyTriInfo->FaceNeighbors[i > 0 ? (i - 1) : 2];
    if (neigh_indexL >= 0)
      AssignRecur(piTriListIn, psTriInfos, neigh_indexL, pGroup);
    if (neigh_indexR >= 0)
      AssignRecur(piTriListIn, psTriInfos, neigh_indexR, pGroup);
  }

  return TTRUE;
}

///////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////

static tbool CompareSubGroups(const SSubGroup *pg1, const SSubGroup *pg2);
static void QuickSort(int *pSortBuffer, int iLeft, int iRight, unsigned int uSeed);
static STSpace EvalTspace(const int face_indices[],
                          const int iFaces,
                          const int piTriListIn[],
                          const STriInfo pTriInfos[],
                          const SMikkTSpaceContext *pContext,
                          const int iVertexRepresentitive);

static tbool GenerateTSpaces(STSpace psTspace[],
                             const STriInfo pTriInfos[],
                             const SGroup pGroups[],
                             const int iNrActiveGroups,
                             const int piTriListIn[],
                             const float fThresCos,
                             const SMikkTSpaceContext *pContext)
{
  STSpace *pSubGroupTspace = NULL;
  SSubGroup *pUniSubGroups = NULL;
  int *pTmpMembers = NULL;
  int iMaxNrFaces = 0, g = 0, i = 0;
  for (g = 0; g < iNrActiveGroups; g++)
    if (iMaxNrFaces < pGroups[g].iNrFaces)
      iMaxNrFaces = pGroups[g].iNrFaces;

  if (iMaxNrFaces == 0)
    return TTRUE;

  // make initial allocations
  pSubGroupTspace = (STSpace *)malloc(sizeof(STSpace) * iMaxNrFaces);
  pUniSubGroups = (SSubGroup *)malloc(sizeof(SSubGroup) * iMaxNrFaces);
  pTmpMembers = (int *)malloc(sizeof(int) * iMaxNrFaces);
  if (pSubGroupTspace == NULL || pUniSubGroups == NULL || pTmpMembers == NULL) {
    if (pSubGroupTspace != NULL)
      free(pSubGroupTspace);
    if (pUniSubGroups != NULL)
      free(pUniSubGroups);
    if (pTmpMembers != NULL)
      free(pTmpMembers);
    return TFALSE;
  }

  for (g = 0; g < iNrActiveGroups; g++) {
    const SGroup *pGroup = &pGroups[g];
    int iUniqueSubGroups = 0, s = 0;

    for (i = 0; i < pGroup->iNrFaces; i++)  // triangles
    {
      const int f = pGroup->pFaceIndices[i];  // triangle number
      int index = -1, iVertIndex = -1, iOF_1 = -1, iMembers = 0, j = 0, l = 0;
      SSubGroup tmp_group;
      tbool bFound;
      SVec3 n, vOs, vOt;
      if (pTriInfos[f].AssignedGroup[0] == pGroup)
        index = 0;
      else if (pTriInfos[f].AssignedGroup[1] == pGroup)
        index = 1;
      else if (pTriInfos[f].AssignedGroup[2] == pGroup)
        index = 2;
      assert(index >= 0 && index < 3);

      iVertIndex = piTriListIn[f * 3 + index];
      assert(iVertIndex == pGroup->iVertexRepresentitive);

      // is normalized already
      n = GetNormal(pContext, iVertIndex);

      // project
      vOs = NormalizeSafe(vsub(pTriInfos[f].vOs, vscale(vdot(n, pTriInfos[f].vOs), n)));
      vOt = NormalizeSafe(vsub(pTriInfos[f].vOt, vscale(vdot(n, pTriInfos[f].vOt), n)));

      // original face number
      iOF_1 = pTriInfos[f].iOrgFaceNumber;

      iMembers = 0;
      for (j = 0; j < pGroup->iNrFaces; j++) {
        const int t = pGroup->pFaceIndices[j];  // triangle number
        const int iOF_2 = pTriInfos[t].iOrgFaceNumber;

        // project
        SVec3 vOs2 = NormalizeSafe(vsub(pTriInfos[t].vOs, vscale(vdot(n, pTriInfos[t].vOs), n)));
        SVec3 vOt2 = NormalizeSafe(vsub(pTriInfos[t].vOt, vscale(vdot(n, pTriInfos[t].vOt), n)));

        {
          const tbool bAny = ((pTriInfos[f].iFlag | pTriInfos[t].iFlag) & GROUP_WITH_ANY) != 0 ?
                                 TTRUE :
                                 TFALSE;
          // make sure triangles which belong to the same quad are joined.
          const tbool bSameOrgFace = iOF_1 == iOF_2 ? TTRUE : TFALSE;

          const float fCosS = vdot(vOs, vOs2);
          const float fCosT = vdot(vOt, vOt2);

          assert(f != t || bSameOrgFace);  // sanity check
          if (bAny || bSameOrgFace || (fCosS > fThresCos && fCosT > fThresCos))
            pTmpMembers[iMembers++] = t;
        }
      }

      // sort pTmpMembers
      tmp_group.iNrFaces = iMembers;
      tmp_group.pTriMembers = pTmpMembers;
      if (iMembers > 1) {
        unsigned int uSeed = INTERNAL_RND_SORT_SEED;  // could replace with a random seed?
        QuickSort(pTmpMembers, 0, iMembers - 1, uSeed);
      }

      // look for an existing match
      bFound = TFALSE;
      l = 0;
      while (l < iUniqueSubGroups && !bFound) {
        bFound = CompareSubGroups(&tmp_group, &pUniSubGroups[l]);
        if (!bFound)
          ++l;
      }

      assert(bFound || l == iUniqueSubGroups);

      // if no match was found we allocate a new subgroup
      if (!bFound) {
        // insert new subgroup
        int *pIndices = (int *)malloc(sizeof(int) * iMembers);
        if (pIndices == NULL) {
          // clean up and return false
          int s = 0;
          for (s = 0; s < iUniqueSubGroups; s++)
            free(pUniSubGroups[s].pTriMembers);
          free(pUniSubGroups);
          free(pTmpMembers);
          free(pSubGroupTspace);
          return TFALSE;
        }
        pUniSubGroups[iUniqueSubGroups].iNrFaces = iMembers;
        pUniSubGroups[iUniqueSubGroups].pTriMembers = pIndices;
        memcpy(pIndices, tmp_group.pTriMembers, sizeof(int) * iMembers);
        pSubGroupTspace[iUniqueSubGroups] = EvalTspace(tmp_group.pTriMembers,
                                                       iMembers,
                                                       piTriListIn,
                                                       pTriInfos,
                                                       pContext,
                                                       pGroup->iVertexRepresentitive);
        ++iUniqueSubGroups;
      }

      // output tspace
      {
        const int iOffs = pTriInfos[f].iTSpacesOffs;
        const int iVert = pTriInfos[f].vert_num[index];
        STSpace *pTS_out = &psTspace[iOffs + iVert];
        assert(pTS_out->iCounter < 2);
        assert(((pTriInfos[f].iFlag & ORIENT_PRESERVING) != 0) == pGroup->bOrientPreservering);
        if (pTS_out->iCounter == 1) {
          *pTS_out = AvgTSpace(pTS_out, &pSubGroupTspace[l]);
          pTS_out->iCounter = 2;  // update counter
          pTS_out->bOrient = pGroup->bOrientPreservering;
        }
        else {
          assert(pTS_out->iCounter == 0);
          *pTS_out = pSubGroupTspace[l];
          pTS_out->iCounter = 1;  // update counter
          pTS_out->bOrient = pGroup->bOrientPreservering;
        }
      }
    }

    // clean up
    for (s = 0; s < iUniqueSubGroups; s++)
      free(pUniSubGroups[s].pTriMembers);
  }

  // clean up
  free(pUniSubGroups);
  free(pTmpMembers);
  free(pSubGroupTspace);

  return TTRUE;
}

static STSpace EvalTspace(const int face_indices[],
                          const int iFaces,
                          const int piTriListIn[],
                          const STriInfo pTriInfos[],
                          const SMikkTSpaceContext *pContext,
                          const int iVertexRepresentitive)
{
  STSpace res;
  float fAngleSum = 0;
  int face = 0;
  res.vOs.x = 0.0f;
  res.vOs.y = 0.0f;
  res.vOs.z = 0.0f;
  res.vOt.x = 0.0f;
  res.vOt.y = 0.0f;
  res.vOt.z = 0.0f;
  res.fMagS = 0;
  res.fMagT = 0;

  for (face = 0; face < iFaces; face++) {
    const int f = face_indices[face];

    // only valid triangles get to add their contribution
    if ((pTriInfos[f].iFlag & GROUP_WITH_ANY) == 0) {
      SVec3 n, vOs, vOt, p0, p1, p2, v1, v2;
      float fCos, fAngle, fMagS, fMagT;
      int i = -1, index = -1, i0 = -1, i1 = -1, i2 = -1;
      if (piTriListIn[3 * f + 0] == iVertexRepresentitive)
        i = 0;
      else if (piTriListIn[3 * f + 1] == iVertexRepresentitive)
        i = 1;
      else if (piTriListIn[3 * f + 2] == iVertexRepresentitive)
        i = 2;
      assert(i >= 0 && i < 3);

      // project
      index = piTriListIn[3 * f + i];
      n = GetNormal(pContext, index);
      vOs = NormalizeSafe(vsub(pTriInfos[f].vOs, vscale(vdot(n, pTriInfos[f].vOs), n)));
      vOt = NormalizeSafe(vsub(pTriInfos[f].vOt, vscale(vdot(n, pTriInfos[f].vOt), n)));

      i2 = piTriListIn[3 * f + (i < 2 ? (i + 1) : 0)];
      i1 = piTriListIn[3 * f + i];
      i0 = piTriListIn[3 * f + (i > 0 ? (i - 1) : 2)];

      p0 = GetPosition(pContext, i0);
      p1 = GetPosition(pContext, i1);
      p2 = GetPosition(pContext, i2);
      v1 = vsub(p0, p1);
      v2 = vsub(p2, p1);

      // project
      v1 = NormalizeSafe(vsub(v1, vscale(vdot(n, v1), n)));
      v2 = NormalizeSafe(vsub(v2, vscale(vdot(n, v2), n)));

      // weight contribution by the angle
      // between the two edge vectors
      fCos = vdot(v1, v2);
      fCos = fCos > 1 ? 1 : (fCos < (-1) ? (-1) : fCos);
      fAngle = (float)acos(fCos);
      fMagS = pTriInfos[f].fMagS;
      fMagT = pTriInfos[f].fMagT;

      res.vOs = vadd(res.vOs, vscale(fAngle, vOs));
      res.vOt = vadd(res.vOt, vscale(fAngle, vOt));
      res.fMagS += (fAngle * fMagS);
      res.fMagT += (fAngle * fMagT);
      fAngleSum += fAngle;
    }
  }

  // normalize
  res.vOs = NormalizeSafe(res.vOs);
  res.vOt = NormalizeSafe(res.vOt);
  if (fAngleSum > 0) {
    res.fMagS /= fAngleSum;
    res.fMagT /= fAngleSum;
  }

  return res;
}

static tbool CompareSubGroups(const SSubGroup *pg1, const SSubGroup *pg2)
{
  tbool bStillSame = TTRUE;
  int i = 0;
  if (pg1->iNrFaces != pg2->iNrFaces)
    return TFALSE;
  while (i < pg1->iNrFaces && bStillSame) {
    bStillSame = pg1->pTriMembers[i] == pg2->pTriMembers[i] ? TTRUE : TFALSE;
    if (bStillSame)
      ++i;
  }
  return bStillSame;
}

static void QuickSort(int *pSortBuffer, int iLeft, int iRight, unsigned int uSeed)
{
  int iL, iR, n, index, iMid, iTmp;

  // Random
  unsigned int t = uSeed & 31;
  t = rotl(uSeed, t);
  uSeed = uSeed + t + 3;
  // Random end

  iL = iLeft;
  iR = iRight;
  n = (iR - iL) + 1;
  assert(n >= 0);
  index = (int)(uSeed % (unsigned int)n);

  iMid = pSortBuffer[index + iL];

  do {
    while (pSortBuffer[iL] < iMid)
      ++iL;
    while (pSortBuffer[iR] > iMid)
      --iR;

    if (iL <= iR) {
      iTmp = pSortBuffer[iL];
      pSortBuffer[iL] = pSortBuffer[iR];
      pSortBuffer[iR] = iTmp;
      ++iL;
      --iR;
    }
  } while (iL <= iR);

  if (iLeft < iR)
    QuickSort(pSortBuffer, iLeft, iR, uSeed);
  if (iL < iRight)
    QuickSort(pSortBuffer, iL, iRight, uSeed);
}

/////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////

static void QuickSortEdges(
    SEdge *pSortBuffer, int iLeft, int iRight, const int channel, unsigned int uSeed);
static void GetEdge(int *i0_out,
                    int *i1_out,
                    int *edgenum_out,
                    const int indices[],
                    const int i0_in,
                    const int i1_in);

static void BuildNeighborsFast(STriInfo pTriInfos[],
                               SEdge *pEdges,
                               const int piTriListIn[],
                               const int iNrTrianglesIn)
{
  // build array of edges
  unsigned int uSeed = INTERNAL_RND_SORT_SEED;  // could replace with a random seed?
  int iEntries = 0, iCurStartIndex = -1, f = 0, i = 0;
  for (f = 0; f < iNrTrianglesIn; f++)
    for (i = 0; i < 3; i++) {
      const int i0 = piTriListIn[f * 3 + i];
      const int i1 = piTriListIn[f * 3 + (i < 2 ? (i + 1) : 0)];
      pEdges[f * 3 + i].i0 = i0 < i1 ? i0 : i1;     // put minimum index in i0
      pEdges[f * 3 + i].i1 = !(i0 < i1) ? i0 : i1;  // put maximum index in i1
      pEdges[f * 3 + i].f = f;                      // record face number
    }

  // sort over all edges by i0, this is the pricey one.
  QuickSortEdges(pEdges, 0, iNrTrianglesIn * 3 - 1, 0, uSeed);  // sort channel 0 which is i0

  // sub sort over i1, should be fast.
  // could replace this with a 64 bit int sort over (i0,i1)
  // with i0 as msb in the quick-sort call above.
  iEntries = iNrTrianglesIn * 3;
  iCurStartIndex = 0;
  for (i = 1; i < iEntries; i++) {
    if (pEdges[iCurStartIndex].i0 != pEdges[i].i0) {
      const int iL = iCurStartIndex;
      const int iR = i - 1;
      // const int iElems = i-iL;
      iCurStartIndex = i;
      QuickSortEdges(pEdges, iL, iR, 1, uSeed);  // sort channel 1 which is i1
    }
  }

  // sub sort over f, which should be fast.
  // this step is to remain compliant with BuildNeighborsSlow() when
  // more than 2 triangles use the same edge (such as a butterfly topology).
  iCurStartIndex = 0;
  for (i = 1; i < iEntries; i++) {
    if (pEdges[iCurStartIndex].i0 != pEdges[i].i0 || pEdges[iCurStartIndex].i1 != pEdges[i].i1) {
      const int iL = iCurStartIndex;
      const int iR = i - 1;
      // const int iElems = i-iL;
      iCurStartIndex = i;
      QuickSortEdges(pEdges, iL, iR, 2, uSeed);  // sort channel 2 which is f
    }
  }

  // pair up, adjacent triangles
  for (i = 0; i < iEntries; i++) {
    const int i0 = pEdges[i].i0;
    const int i1 = pEdges[i].i1;
    const int f = pEdges[i].f;
    tbool bUnassigned_A;

    int i0_A, i1_A;
    int edgenum_A, edgenum_B = 0;  // 0,1 or 2
    GetEdge(&i0_A,
            &i1_A,
            &edgenum_A,
            &piTriListIn[f * 3],
            i0,
            i1);  // resolve index ordering and edge_num
    bUnassigned_A = pTriInfos[f].FaceNeighbors[edgenum_A] == -1 ? TTRUE : TFALSE;

    if (bUnassigned_A) {
      // get true index ordering
      int j = i + 1, t;
      tbool bNotFound = TTRUE;
      while (j < iEntries && i0 == pEdges[j].i0 && i1 == pEdges[j].i1 && bNotFound) {
        tbool bUnassigned_B;
        int i0_B, i1_B;
        t = pEdges[j].f;
        // flip i0_B and i1_B
        GetEdge(&i1_B,
                &i0_B,
                &edgenum_B,
                &piTriListIn[t * 3],
                pEdges[j].i0,
                pEdges[j].i1);  // resolve index ordering and edge_num
        // assert(!(i0_A==i1_B && i1_A==i0_B));
        bUnassigned_B = pTriInfos[t].FaceNeighbors[edgenum_B] == -1 ? TTRUE : TFALSE;
        if (i0_A == i0_B && i1_A == i1_B && bUnassigned_B)
          bNotFound = TFALSE;
        else
          ++j;
      }

      if (!bNotFound) {
        int t = pEdges[j].f;
        pTriInfos[f].FaceNeighbors[edgenum_A] = t;
        // assert(pTriInfos[t].FaceNeighbors[edgenum_B]==-1);
        pTriInfos[t].FaceNeighbors[edgenum_B] = f;
      }
    }
  }
}

static void BuildNeighborsSlow(STriInfo pTriInfos[],
                               const int piTriListIn[],
                               const int iNrTrianglesIn)
{
  int f = 0, i = 0;
  for (f = 0; f < iNrTrianglesIn; f++) {
    for (i = 0; i < 3; i++) {
      // if unassigned
      if (pTriInfos[f].FaceNeighbors[i] == -1) {
        const int i0_A = piTriListIn[f * 3 + i];
        const int i1_A = piTriListIn[f * 3 + (i < 2 ? (i + 1) : 0)];

        // search for a neighbor
        tbool bFound = TFALSE;
        int t = 0, j = 0;
        while (!bFound && t < iNrTrianglesIn) {
          if (t != f) {
            j = 0;
            while (!bFound && j < 3) {
              // in rev order
              const int i1_B = piTriListIn[t * 3 + j];
              const int i0_B = piTriListIn[t * 3 + (j < 2 ? (j + 1) : 0)];
              // assert(!(i0_A==i1_B && i1_A==i0_B));
              if (i0_A == i0_B && i1_A == i1_B)
                bFound = TTRUE;
              else
                ++j;
            }
          }

          if (!bFound)
            ++t;
        }

        // assign neighbors
        if (bFound) {
          pTriInfos[f].FaceNeighbors[i] = t;
          // assert(pTriInfos[t].FaceNeighbors[j]==-1);
          pTriInfos[t].FaceNeighbors[j] = f;
        }
      }
    }
  }
}

static void QuickSortEdges(
    SEdge *pSortBuffer, int iLeft, int iRight, const int channel, unsigned int uSeed)
{
  unsigned int t;
  int iL, iR, n, index, iMid;

  // early out
  SEdge sTmp;
  const int iElems = iRight - iLeft + 1;
  if (iElems < 2)
    return;
  else if (iElems == 2) {
    if (pSortBuffer[iLeft].array[channel] > pSortBuffer[iRight].array[channel]) {
      sTmp = pSortBuffer[iLeft];
      pSortBuffer[iLeft] = pSortBuffer[iRight];
      pSortBuffer[iRight] = sTmp;
    }
    return;
  }
  else if (iElems < 16) {
    int i, j;
    for (i = 0; i < iElems - 1; i++) {
      for (j = 0; j < iElems - i - 1; j++) {
        int index = iLeft + j;
        if (pSortBuffer[index].array[channel] > pSortBuffer[index + 1].array[channel]) {
          sTmp = pSortBuffer[index];
          pSortBuffer[index] = pSortBuffer[index + 1];
          pSortBuffer[index + 1] = sTmp;
        }
      }
    }
    return;
  }

  // Random
  t = uSeed & 31;
  t = rotl(uSeed, t);
  uSeed = uSeed + t + 3;
  // Random end

  iL = iLeft;
  iR = iRight;
  n = (iR - iL) + 1;
  assert(n >= 0);
  index = (int)(uSeed % (unsigned int)n);

  iMid = pSortBuffer[index + iL].array[channel];

  do {
    while (pSortBuffer[iL].array[channel] < iMid)
      ++iL;
    while (pSortBuffer[iR].array[channel] > iMid)
      --iR;

    if (iL <= iR) {
      sTmp = pSortBuffer[iL];
      pSortBuffer[iL] = pSortBuffer[iR];
      pSortBuffer[iR] = sTmp;
      ++iL;
      --iR;
    }
  } while (iL <= iR);

  if (iLeft < iR)
    QuickSortEdges(pSortBuffer, iLeft, iR, channel, uSeed);
  if (iL < iRight)
    QuickSortEdges(pSortBuffer, iL, iRight, channel, uSeed);
}

// resolve ordering and edge number
static void GetEdge(int *i0_out,
                    int *i1_out,
                    int *edgenum_out,
                    const int indices[],
                    const int i0_in,
                    const int i1_in)
{
  *edgenum_out = -1;

  // test if first index is on the edge
  if (indices[0] == i0_in || indices[0] == i1_in) {
    // test if second index is on the edge
    if (indices[1] == i0_in || indices[1] == i1_in) {
      edgenum_out[0] = 0;  // first edge
      i0_out[0] = indices[0];
      i1_out[0] = indices[1];
    }
    else {
      edgenum_out[0] = 2;  // third edge
      i0_out[0] = indices[2];
      i1_out[0] = indices[0];
    }
  }
  else {
    // only second and third index is on the edge
    edgenum_out[0] = 1;  // second edge
    i0_out[0] = indices[1];
    i1_out[0] = indices[2];
  }
}

/////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////// Degenerate triangles ////////////////////////////////////

static void DegenPrologue(STriInfo pTriInfos[],
                          int piTriList_out[],
                          const int iNrTrianglesIn,
                          const int iTotTris)
{
  int iNextGoodTriangleSearchIndex = -1;
  tbool bStillFindingGoodOnes;

  // locate quads with only one good triangle
  int t = 0;
  while (t < (iTotTris - 1)) {
    const int iFO_a = pTriInfos[t].iOrgFaceNumber;
    const int iFO_b = pTriInfos[t + 1].iOrgFaceNumber;
    if (iFO_a == iFO_b)  // this is a quad
    {
      const tbool bIsDeg_a = (pTriInfos[t].iFlag & MARK_DEGENERATE) != 0 ? TTRUE : TFALSE;
      const tbool bIsDeg_b = (pTriInfos[t + 1].iFlag & MARK_DEGENERATE) != 0 ? TTRUE : TFALSE;
      if ((bIsDeg_a ^ bIsDeg_b) != 0) {
        pTriInfos[t].iFlag |= QUAD_ONE_DEGEN_TRI;
        pTriInfos[t + 1].iFlag |= QUAD_ONE_DEGEN_TRI;
      }
      t += 2;
    }
    else
      ++t;
  }

  // reorder list so all degen triangles are moved to the back
  // without reordering the good triangles
  iNextGoodTriangleSearchIndex = 1;
  t = 0;
  bStillFindingGoodOnes = TTRUE;
  while (t < iNrTrianglesIn && bStillFindingGoodOnes) {
    const tbool bIsGood = (pTriInfos[t].iFlag & MARK_DEGENERATE) == 0 ? TTRUE : TFALSE;
    if (bIsGood) {
      if (iNextGoodTriangleSearchIndex < (t + 2))
        iNextGoodTriangleSearchIndex = t + 2;
    }
    else {
      int t0, t1;
      // search for the first good triangle.
      tbool bJustADegenerate = TTRUE;
      while (bJustADegenerate && iNextGoodTriangleSearchIndex < iTotTris) {
        const tbool bIsGood = (pTriInfos[iNextGoodTriangleSearchIndex].iFlag & MARK_DEGENERATE) ==
                                      0 ?
                                  TTRUE :
                                  TFALSE;
        if (bIsGood)
          bJustADegenerate = TFALSE;
        else
          ++iNextGoodTriangleSearchIndex;
      }

      t0 = t;
      t1 = iNextGoodTriangleSearchIndex;
      ++iNextGoodTriangleSearchIndex;
      assert(iNextGoodTriangleSearchIndex > (t + 1));

      // swap triangle t0 and t1
      if (!bJustADegenerate) {
        int i = 0;
        for (i = 0; i < 3; i++) {
          const int index = piTriList_out[t0 * 3 + i];
          piTriList_out[t0 * 3 + i] = piTriList_out[t1 * 3 + i];
          piTriList_out[t1 * 3 + i] = index;
        }
        {
          const STriInfo tri_info = pTriInfos[t0];
          pTriInfos[t0] = pTriInfos[t1];
          pTriInfos[t1] = tri_info;
        }
      }
      else
        bStillFindingGoodOnes = TFALSE;  // this is not supposed to happen
    }

    if (bStillFindingGoodOnes)
      ++t;
  }

  assert(bStillFindingGoodOnes);  // code will still work.
  assert(iNrTrianglesIn == t);
}

typedef struct VertReverseLookupContext {
  tbool bIsInitialized;
  int *pLookup;
  int iMaxVertIndex;
} VertReverseLookupContext;

static void GenerateReverseLookup(const int piTriListIn[],
                                  const int iNrTrianglesIn,
                                  VertReverseLookupContext *pLookupCtx)
{
  int t;
  // Figure out what size of lookup array we need.
  pLookupCtx->iMaxVertIndex = -1;
  for (t = 0; t < 3 * iNrTrianglesIn; t++) {
    int iVertIndex = piTriListIn[t];
    if (iVertIndex > pLookupCtx->iMaxVertIndex) {
      pLookupCtx->iMaxVertIndex = iVertIndex;
    }
  }
  // Allocate memory.
  if (pLookupCtx->iMaxVertIndex < 1) {
    // Nothing to allocate, all triangles are degenerate.
    return;
  }
  pLookupCtx->pLookup = malloc(sizeof(int) * (pLookupCtx->iMaxVertIndex + 1));
  if (pLookupCtx->pLookup == NULL) {
    // Most likely run out of memory.
    return;
  }
  // Fill in lookup.
  for (t = 0; t <= pLookupCtx->iMaxVertIndex; t++) {
    pLookupCtx->pLookup[t] = -1;
  }
  for (t = 0; t < 3 * iNrTrianglesIn; t++) {
    int iVertIndex = piTriListIn[t];
    if (pLookupCtx->pLookup[iVertIndex] != -1) {
      continue;
    }
    pLookupCtx->pLookup[iVertIndex] = t;
  }
}

static int LookupVertexIndexFromGoodTriangle(VertReverseLookupContext *pLookupCtx,
                                             int piTriListIn[],
                                             const int iNrTrianglesIn,
                                             const int iVertexIndex)
{
  // Allocate lookup on demand.
  if (!pLookupCtx->bIsInitialized) {
    GenerateReverseLookup(piTriListIn, iNrTrianglesIn, pLookupCtx);
    pLookupCtx->bIsInitialized = TTRUE;
  }
  // Make sure vertex index is in the mapping.
  if (iVertexIndex > pLookupCtx->iMaxVertIndex) {
    return -1;
  }
  if (pLookupCtx->pLookup == NULL) {
    return -1;
  }
  // Perform actual lookup.
  return pLookupCtx->pLookup[iVertexIndex];
}

static void FreeReverseLookup(VertReverseLookupContext *pLookupCtx)
{
  if (!pLookupCtx->bIsInitialized) {
    return;
  }
  if (pLookupCtx->pLookup != NULL) {
    free(pLookupCtx->pLookup);
  }
}

static void DegenEpilogue(STSpace psTspace[],
                          STriInfo pTriInfos[],
                          int piTriListIn[],
                          const SMikkTSpaceContext *pContext,
                          const int iNrTrianglesIn,
                          const int iTotTris)
{
  int t = 0, i = 0;
  VertReverseLookupContext lookupCtx = {TFALSE};
  // deal with degenerate triangles
  // punishment for degenerate triangles is O(iNrTrianglesIn) extra memory.
  for (t = iNrTrianglesIn; t < iTotTris; t++) {
    // degenerate triangles on a quad with one good triangle are skipped
    // here but processed in the next loop
    const tbool bSkip = (pTriInfos[t].iFlag & QUAD_ONE_DEGEN_TRI) != 0 ? TTRUE : TFALSE;
    if (bSkip) {
      continue;
    }

    for (i = 0; i < 3; i++) {
      const int index1 = piTriListIn[t * 3 + i];
      int j = LookupVertexIndexFromGoodTriangle(&lookupCtx, piTriListIn, iNrTrianglesIn, index1);
      if (j < 0) {
        // Matching vertex from good triangle is not found.
        continue;
      }

      const int iTri = j / 3;
      const int iVert = j % 3;
      const int iSrcVert = pTriInfos[iTri].vert_num[iVert];
      const int iSrcOffs = pTriInfos[iTri].iTSpacesOffs;
      const int iDstVert = pTriInfos[t].vert_num[i];
      const int iDstOffs = pTriInfos[t].iTSpacesOffs;
      // copy tspace
      psTspace[iDstOffs + iDstVert] = psTspace[iSrcOffs + iSrcVert];
    }
  }
  FreeReverseLookup(&lookupCtx);

  // deal with degenerate quads with one good triangle
  for (t = 0; t < iNrTrianglesIn; t++) {
    // this triangle belongs to a quad where the
    // other triangle is degenerate
    if ((pTriInfos[t].iFlag & QUAD_ONE_DEGEN_TRI) != 0) {
      SVec3 vDstP;
      int iOrgF = -1, i = 0;
      tbool bNotFound;
      unsigned char *pV = pTriInfos[t].vert_num;
      int iFlag = (1 << pV[0]) | (1 << pV[1]) | (1 << pV[2]);
      int iMissingIndex = 0;
      if ((iFlag & 2) == 0)
        iMissingIndex = 1;
      else if ((iFlag & 4) == 0)
        iMissingIndex = 2;
      else if ((iFlag & 8) == 0)
        iMissingIndex = 3;

      iOrgF = pTriInfos[t].iOrgFaceNumber;
      vDstP = GetPosition(pContext, MakeIndex(iOrgF, iMissingIndex));
      bNotFound = TTRUE;
      i = 0;
      while (bNotFound && i < 3) {
        const int iVert = pV[i];
        const SVec3 vSrcP = GetPosition(pContext, MakeIndex(iOrgF, iVert));
        if (veq(vSrcP, vDstP) == TTRUE) {
          const int iOffs = pTriInfos[t].iTSpacesOffs;
          psTspace[iOffs + iMissingIndex] = psTspace[iOffs + iVert];
          bNotFound = TFALSE;
        }
        else
          ++i;
      }
      assert(!bNotFound);
    }
  }
}