static tbool GenerateTSpaces()

in shared/ext/mikktspace.cpp [1195:1362]
130 lines of code
39 McCabe index (conditional complexity)

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

		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);
			_Analysis_assume_(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
					for (int 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 (int s=0; s<iUniqueSubGroups; s++)
			free(pUniSubGroups[s].pTriMembers);
		iUniqueTspaces += iUniqueSubGroups;
	}

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

	return TTRUE;
}