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