mikktspace.c

Go to the documentation of this file.

#include <assert.h>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <float.h>
#include <stdlib.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

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

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

static 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;
}


static 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;
}

static 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;
}

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

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

static SVec3            Normalize( const SVec3 v )
{
        return vscale(1 / Length(v), v);
}

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


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

static tbool VNotZero(const SVec3 v)
{
        // might change this to an epsilon based test
        return NotZero(v.x) || NotZero(v.y) || NotZero(v.z);
}



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;

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

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

static 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);
                if( VNotZero(ts_res.vOs) ) ts_res.vOs = Normalize(ts_res.vOs);
                if( VNotZero(ts_res.vOt) ) ts_res.vOt = Normalize(ts_res.vOt);
        }

        return ts_res;
}



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


// degen triangles
void DegenPrologue(STriInfo pTriInfos[], int piTriList_out[], const int iNrTrianglesIn, const int iTotTris);
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 = (float) cos((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)*iNrTrianglesIn*3);
        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.

                /*// 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;
                }*/

                // 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;
}


typedef struct
{
        float vert[3];
        int index;
} STmpVert;

const int g_iCells = 2048;

#ifdef _MSC_VER
        #define NOINLINE __declspec(noinline)
#else
        #define NOINLINE __attribute__ ((noinline))
#endif

// it is IMPORTANT that this function is called to evaluate the hash since
// inlining could potentially reorder instructions and generate different
// results for the same effective input value fVal.
NOINLINE int FindGridCell(const float fMin, const float fMax, const float fVal)
{
        const float fIndex = g_iCells * ((fVal-fMin)/(fMax-fMin));
        const int iIndex = fIndex<0?0:((int)fIndex);
        return iIndex<g_iCells?iIndex:(g_iCells-1);
}

void MergeVertsFast(int piTriList_in_and_out[], STmpVert pTmpVert[], const SMikkTSpaceContext * pContext, const int iL_in, const int iR_in);
void MergeVertsSlow(int piTriList_in_and_out[], const SMikkTSpaceContext * pContext, const int pTable[], const int iEntries);
void GenerateSharedVerticesIndexListSlow(int piTriList_in_and_out[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn);

void GenerateSharedVerticesIndexList(int piTriList_in_and_out[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn)
{

        // Generate bounding box
        int * piHashTable=NULL, * piHashCount=NULL, * piHashOffsets=NULL, * piHashCount2=NULL;
        STmpVert * pTmpVert = NULL;
        int i=0, iChannel=0, k=0, e=0;
        int iMaxCount=0;
        SVec3 vMin = GetPosition(pContext, 0), vMax = vMin, vDim;
        float fMin, fMax;
        for(i=1; i<(iNrTrianglesIn*3); i++)
        {
                const int index = piTriList_in_and_out[i];

                const SVec3 vP = GetPosition(pContext, index);
                if(vMin.x > vP.x) vMin.x = vP.x;
                else if(vMax.x < vP.x) vMax.x = vP.x;
                if(vMin.y > vP.y) vMin.y = vP.y;
                else if(vMax.y < vP.y) vMax.y = vP.y;
                if(vMin.z > vP.z) vMin.z = vP.z;
                else if(vMax.z < vP.z) vMax.z = vP.z;
        }

        vDim = vsub(vMax,vMin);
        iChannel = 0;
        fMin = vMin.x; fMax=vMax.x;
        if(vDim.y>vDim.x && vDim.y>vDim.z)
        {
                iChannel=1;
                fMin = vMin.y, fMax=vMax.y;
        }
        else if(vDim.z>vDim.x)
        {
                iChannel=2;
                fMin = vMin.z, fMax=vMax.z;
        }

        // make allocations
        piHashTable = (int *) malloc(sizeof(int)*iNrTrianglesIn*3);
        piHashCount = (int *) malloc(sizeof(int)*g_iCells);
        piHashOffsets = (int *) malloc(sizeof(int)*g_iCells);
        piHashCount2 = (int *) malloc(sizeof(int)*g_iCells);

        if(piHashTable==NULL || piHashCount==NULL || piHashOffsets==NULL || piHashCount2==NULL)
        {
                if(piHashTable!=NULL) free(piHashTable);
                if(piHashCount!=NULL) free(piHashCount);
                if(piHashOffsets!=NULL) free(piHashOffsets);
                if(piHashCount2!=NULL) free(piHashCount2);
                GenerateSharedVerticesIndexListSlow(piTriList_in_and_out, pContext, iNrTrianglesIn);
                return;
        }
        memset(piHashCount, 0, sizeof(int)*g_iCells);
        memset(piHashCount2, 0, sizeof(int)*g_iCells);

        // count amount of elements in each cell unit
        for(i=0; i<(iNrTrianglesIn*3); i++)
        {
                const int index = piTriList_in_and_out[i];
                const SVec3 vP = GetPosition(pContext, index);
                const float fVal = iChannel==0 ? vP.x : (iChannel==1 ? vP.y : vP.z);
                const int iCell = FindGridCell(fMin, fMax, fVal);
                ++piHashCount[iCell];
        }

        // evaluate start index of each cell.
        piHashOffsets[0]=0;
        for(k=1; k<g_iCells; k++)
                piHashOffsets[k]=piHashOffsets[k-1]+piHashCount[k-1];

        // insert vertices
        for(i=0; i<(iNrTrianglesIn*3); i++)
        {
                const int index = piTriList_in_and_out[i];
                const SVec3 vP = GetPosition(pContext, index);
                const float fVal = iChannel==0 ? vP.x : (iChannel==1 ? vP.y : vP.z);
                const int iCell = FindGridCell(fMin, fMax, fVal);
                int * pTable = NULL;

                assert(piHashCount2[iCell]<piHashCount[iCell]);
                pTable = &piHashTable[piHashOffsets[iCell]];
                pTable[piHashCount2[iCell]] = i;        // vertex i has been inserted.
                ++piHashCount2[iCell];
        }
        for(k=0; k<g_iCells; k++)
                assert(piHashCount2[k] == piHashCount[k]);      // verify the count
        free(piHashCount2);

        // find maximum amount of entries in any hash entry
        iMaxCount = piHashCount[0];
        for(k=1; k<g_iCells; k++)
                if(iMaxCount<piHashCount[k])
                        iMaxCount=piHashCount[k];
        pTmpVert = (STmpVert *) malloc(sizeof(STmpVert)*iMaxCount);
        

        // complete the merge
        for(k=0; k<g_iCells; k++)
        {
                // extract table of cell k and amount of entries in it
                int * pTable = &piHashTable[piHashOffsets[k]];
                const int iEntries = piHashCount[k];
                if(iEntries < 2) continue;

                if(pTmpVert!=NULL)
                {
                        for(e=0; e<iEntries; e++)
                        {
                                int i = pTable[e];
                                const SVec3 vP = GetPosition(pContext, piTriList_in_and_out[i]);
                                pTmpVert[e].vert[0] = vP.x; pTmpVert[e].vert[1] = vP.y;
                                pTmpVert[e].vert[2] = vP.z; pTmpVert[e].index = i;
                        }
                        MergeVertsFast(piTriList_in_and_out, pTmpVert, pContext, 0, iEntries-1);
                }
                else
                        MergeVertsSlow(piTriList_in_and_out, pContext, pTable, iEntries);
        }

        if(pTmpVert!=NULL) { free(pTmpVert); }
        free(piHashTable);
        free(piHashCount);
        free(piHashOffsets);
}

void MergeVertsFast(int piTriList_in_and_out[], STmpVert pTmpVert[], const SMikkTSpaceContext * pContext, const int iL_in, const int iR_in)
{
        // make bbox
        int c=0, l=0, channel=0;
        float fvMin[3], fvMax[3];
        float dx=0, dy=0, dz=0, fSep=0;
        for(c=0; c<3; c++)
        {       fvMin[c]=pTmpVert[iL_in].vert[c]; fvMax[c]=fvMin[c];    }
        for(l=(iL_in+1); l<=iR_in; l++)
                for(c=0; c<3; c++)
                        if(fvMin[c]>pTmpVert[l].vert[c]) fvMin[c]=pTmpVert[l].vert[c];
                        else if(fvMax[c]<pTmpVert[l].vert[c]) fvMax[c]=pTmpVert[l].vert[c];

        dx = fvMax[0]-fvMin[0];
        dy = fvMax[1]-fvMin[1];
        dz = fvMax[2]-fvMin[2];

        channel = 0;
        if(dy>dx && dy>dz) channel=1;
        else if(dz>dx) channel=2;

        fSep = 0.5f*(fvMax[channel]+fvMin[channel]);

        // terminate recursion when the separation/average value
        // is no longer strictly between fMin and fMax values.
        if(fSep>=fvMax[channel] || fSep<=fvMin[channel])
        {
                // complete the weld
                for(l=iL_in; l<=iR_in; l++)
                {
                        int i = pTmpVert[l].index;
                        const int index = piTriList_in_and_out[i];
                        const SVec3 vP = GetPosition(pContext, index);
                        const SVec3 vN = GetNormal(pContext, index);
                        const SVec3 vT = GetTexCoord(pContext, index);

                        tbool bNotFound = TTRUE;
                        int l2=iL_in, i2rec=-1;
                        while(l2<l && bNotFound)
                        {
                                const int i2 = pTmpVert[l2].index;
                                const int index2 = piTriList_in_and_out[i2];
                                const SVec3 vP2 = GetPosition(pContext, index2);
                                const SVec3 vN2 = GetNormal(pContext, index2);
                                const SVec3 vT2 = GetTexCoord(pContext, index2);
                                i2rec=i2;

                                //if(vP==vP2 && vN==vN2 && vT==vT2)
                                if(vP.x==vP2.x && vP.y==vP2.y && vP.z==vP2.z &&
                                        vN.x==vN2.x && vN.y==vN2.y && vN.z==vN2.z &&
                                        vT.x==vT2.x && vT.y==vT2.y && vT.z==vT2.z)
                                        bNotFound = TFALSE;
                                else
                                        ++l2;
                        }
                        
                        // merge if previously found
                        if(!bNotFound)
                                piTriList_in_and_out[i] = piTriList_in_and_out[i2rec];
                }
        }
        else
        {
                int iL=iL_in, iR=iR_in;
                assert((iR_in-iL_in)>0);        // at least 2 entries

                // separate (by fSep) all points between iL_in and iR_in in pTmpVert[]
                while(iL < iR)
                {
                        tbool bReadyLeftSwap = TFALSE, bReadyRightSwap = TFALSE;
                        while((!bReadyLeftSwap) && iL<iR)
                        {
                                assert(iL>=iL_in && iL<=iR_in);
                                bReadyLeftSwap = !(pTmpVert[iL].vert[channel]<fSep);
                                if(!bReadyLeftSwap) ++iL;
                        }
                        while((!bReadyRightSwap) && iL<iR)
                        {
                                assert(iR>=iL_in && iR<=iR_in);
                                bReadyRightSwap = pTmpVert[iR].vert[channel]<fSep;
                                if(!bReadyRightSwap) --iR;
                        }
                        assert( (iL<iR) || !(bReadyLeftSwap && bReadyRightSwap) );

                        if(bReadyLeftSwap && bReadyRightSwap)
                        {
                                const STmpVert sTmp = pTmpVert[iL];
                                assert(iL<iR);
                                pTmpVert[iL] = pTmpVert[iR];
                                pTmpVert[iR] = sTmp;
                                ++iL; --iR;
                        }
                }

                assert(iL==(iR+1) || (iL==iR));
                if(iL==iR)
                {
                        const tbool bReadyRightSwap = pTmpVert[iR].vert[channel]<fSep;
                        if(bReadyRightSwap) ++iL;
                        else --iR;
                }

                // only need to weld when there is more than 1 instance of the (x,y,z)
                if(iL_in < iR)
                        MergeVertsFast(piTriList_in_and_out, pTmpVert, pContext, iL_in, iR);    // weld all left of fSep
                if(iL < iR_in)
                        MergeVertsFast(piTriList_in_and_out, pTmpVert, pContext, iL, iR_in);    // weld all right of (or equal to) fSep
        }
}

void MergeVertsSlow(int piTriList_in_and_out[], const SMikkTSpaceContext * pContext, const int pTable[], const int iEntries)
{
        // this can be optimized further using a tree structure or more hashing.
        int e=0;
        for(e=0; e<iEntries; e++)
        {
                int i = pTable[e];
                const int index = piTriList_in_and_out[i];
                const SVec3 vP = GetPosition(pContext, index);
                const SVec3 vN = GetNormal(pContext, index);
                const SVec3 vT = GetTexCoord(pContext, index);

                tbool bNotFound = TTRUE;
                int e2=0, i2rec=-1;
                while(e2<e && bNotFound)
                {
                        const int i2 = pTable[e2];
                        const int index2 = piTriList_in_and_out[i2];
                        const SVec3 vP2 = GetPosition(pContext, index2);
                        const SVec3 vN2 = GetNormal(pContext, index2);
                        const SVec3 vT2 = GetTexCoord(pContext, index2);
                        i2rec = i2;

                        if(veq(vP,vP2) && veq(vN,vN2) && veq(vT,vT2))
                                bNotFound = TFALSE;
                        else
                                ++e2;
                }
                
                // merge if previously found
                if(!bNotFound)
                        piTriList_in_and_out[i] = piTriList_in_and_out[i2rec];
        }
}

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;
                }
        }
}

int GenerateInitialVerticesIndexList(STriInfo pTriInfos[], int piTriList_out[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn)
{
        int iTSpacesOffs = 0, f=0, t=0;
        int iDstTriIndex = 0;
        for(f=0; f<pContext->m_pInterface->m_getNumFaces(pContext); 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;
}

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;
}

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;
}

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;

void BuildNeighborsFast(STriInfo pTriInfos[], SEdge * pEdges, const int piTriListIn[], const int iNrTrianglesIn);
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;
}

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)*iNrTrianglesIn*3);
                if(pEdges==NULL)
                        BuildNeighborsSlow(pTriInfos, piTriListIn, iNrTrianglesIn);
                else
                {
                        BuildNeighborsFast(pTriInfos, pEdges, piTriListIn, iNrTrianglesIn);
        
                        free(pEdges);
                }
        }
}


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

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;
        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);
                                }
                                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);
                                }

                                // 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;
}

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

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 it's 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;
}


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

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, iUniqueTspaces=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;
        }


        iUniqueTspaces = 0;
        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 = vsub(pTriInfos[f].vOs, vscale(vdot(n,pTriInfos[f].vOs), n));
                        vOt = vsub(pTriInfos[f].vOt, vscale(vdot(n,pTriInfos[f].vOt), n));
                        if( VNotZero(vOs) ) vOs = Normalize(vOs);
                        if( VNotZero(vOt) ) vOt = Normalize(vOt);

                        // 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 = vsub(pTriInfos[t].vOs, vscale(vdot(n,pTriInfos[t].vOs), n));
                                SVec3 vOt2 = vsub(pTriInfos[t].vOt, vscale(vdot(n,pTriInfos[t].vOt), n));
                                if( VNotZero(vOs2) ) vOs2 = Normalize(vOs2);
                                if( VNotZero(vOt2) ) vOt2 = Normalize(vOt2);

                                {
                                        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;
                        }
                        
                        // assign tangent space index
                        assert(bFound || l==iUniqueSubGroups);
                        //piTempTangIndices[f*3+index] = iUniqueTspaces+l;

                        // 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, iMembers*sizeof(int));
                                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 and offset iUniqueTspaces
                for(s=0; s<iUniqueSubGroups; s++)
                        free(pUniSubGroups[s].pTriMembers);
                iUniqueTspaces += iUniqueSubGroups;
                iUniqueSubGroups = 0;
        }

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

        return TTRUE;
}

STSpace EvalTspace(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 = vsub(pTriInfos[f].vOs, vscale(vdot(n,pTriInfos[f].vOs), n));
                        vOt = vsub(pTriInfos[f].vOt, vscale(vdot(n,pTriInfos[f].vOt), n));
                        if( VNotZero(vOs) ) vOs = Normalize(vOs);
                        if( VNotZero(vOt) ) vOt = Normalize(vOt);

                        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 = vsub(v1, vscale(vdot(n,v1),n)); if( VNotZero(v1) ) v1 = Normalize(v1);
                        v2 = vsub(v2, vscale(vdot(n,v2),n)); if( VNotZero(v2) ) v2 = Normalize(v2);

                        // 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
        if( VNotZero(res.vOs) ) res.vOs = Normalize(res.vOs);
        if( VNotZero(res.vOt) ) res.vOt = Normalize(res.vOt);
        if(fAngleSum>0)
        {
                res.fMagS /= fAngleSum;
                res.fMagT /= fAngleSum;
        }

        return res;
}

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;
}

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=(uSeed<<t)|(uSeed>>(32-t));
        uSeed=uSeed+t+3;
        // Random end

        iL=iLeft; iR=iRight;
        n = (iR-iL)+1;
        assert(n>=0);
        index = (int) (uSeed%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);
}


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

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 pricy 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 quicksort 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;
                        }
                }
        }
}

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;
                                }
                        }
                }
        }
}

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;
        }

        // Random
        t=uSeed&31;
        t=(uSeed<<t)|(uSeed>>(32-t));
        uSeed=uSeed+t+3;
        // Random end

        iL=iLeft, iR=iRight;
        n = (iR-iL)+1;
        assert(n>=0);
        index = (int) (uSeed%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
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];
        }
}



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);
}

void DegenEpilogue(STSpace psTspace[], STriInfo pTriInfos[], int piTriListIn[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn, const int iTotTris)
{
        int t=0, i=0;
        // deal with degenerate triangles
        // punishment for degenerate triangles is O(N^2)
        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)
                {
                        for(i=0; i<3; i++)
                        {
                                const int index1 = piTriListIn[t*3+i];
                                // search through the good triangles
                                tbool bNotFound = TTRUE;
                                int j=0;
                                while(bNotFound && j<(3*iNrTrianglesIn))
                                {
                                        const int index2 = piTriListIn[j];
                                        if(index1==index2) bNotFound=TFALSE;
                                        else ++j;
                                }

                                if(!bNotFound)
                                {
                                        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];
                                }
                        }
                }
        }

        // 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);
                }
        }
}