aboutsummaryrefslogtreecommitdiff
path: root/contrib/cgltf-tangents
diff options
context:
space:
mode:
Diffstat (limited to 'contrib/cgltf-tangents')
-rw-r--r--contrib/cgltf-tangents/CMakeLists.txt13
-rw-r--r--contrib/cgltf-tangents/LICENSE79
-rw-r--r--contrib/cgltf-tangents/MikkTSpace/README.md4
-rw-r--r--contrib/cgltf-tangents/MikkTSpace/mikktspace.c1899
-rw-r--r--contrib/cgltf-tangents/MikkTSpace/mikktspace.h145
-rw-r--r--contrib/cgltf-tangents/README.md42
-rw-r--r--contrib/cgltf-tangents/cgltf_tangents.c618
-rw-r--r--contrib/cgltf-tangents/cgltf_tangents.h67
-rw-r--r--contrib/cgltf-tangents/test/CMakeLists.txt11
-rw-r--r--contrib/cgltf-tangents/test/main.c86
10 files changed, 2964 insertions, 0 deletions
diff --git a/contrib/cgltf-tangents/CMakeLists.txt b/contrib/cgltf-tangents/CMakeLists.txt
new file mode 100644
index 0000000..2c0771e
--- /dev/null
+++ b/contrib/cgltf-tangents/CMakeLists.txt
@@ -0,0 +1,13 @@
1cmake_minimum_required(VERSION 3.0)
2
3project(cgltf-tangents)
4
5add_library(cgltf-tangents
6 cgltf_tangents.c
7 MikkTSpace/mikktspace.c)
8
9target_include_directories(cgltf-tangents PUBLIC
10 ${CMAKE_CURRENT_SOURCE_DIR})
11
12target_link_libraries(cgltf-tangents PUBLIC
13 cgltf)
diff --git a/contrib/cgltf-tangents/LICENSE b/contrib/cgltf-tangents/LICENSE
new file mode 100644
index 0000000..7796e37
--- /dev/null
+++ b/contrib/cgltf-tangents/LICENSE
@@ -0,0 +1,79 @@
1This project has two third-party dependencies:
2- MikkTSpace
3- cgltf
4
5The license for this project and its dependencies are included below.
6
7--------------------------------------------------------------------------------
8cgltf-tangents
9--------------------------------------------------------------------------------
10
11Copyright 2022 Marc Sunet
12
13Redistribution and use in source and binary forms, with or without modification,
14are permitted provided that the following conditions are met:
15
161. Redistributions of source code must retain the above copyright notice, this
17list of conditions and the following disclaimer.
18
192. Redistributions in binary form must reproduce the above copyright notice,
20this list of conditions and the following disclaimer in the documentation and/or
21other materials provided with the distribution.
22
23THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
24ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
25WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
26DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR
27ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
28(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
29LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
30ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
31(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
32SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
33
34--------------------------------------------------------------------------------
35MikkTSpace
36--------------------------------------------------------------------------------
37
38Copyright (C) 2011 by Morten S. Mikkelsen
39
40This software is provided 'as-is', without any express or implied
41warranty. In no event will the authors be held liable for any damages
42arising from the use of this software.
43
44Permission is granted to anyone to use this software for any purpose,
45including commercial applications, and to alter it and redistribute it
46freely, subject to the following restrictions:
47
481. The origin of this software must not be misrepresented; you must not
49 claim that you wrote the original software. If you use this software
50 in a product, an acknowledgment in the product documentation would be
51 appreciated but is not required.
52
532. Altered source versions must be plainly marked as such, and must not be
54 misrepresented as being the original software.
55
563. This notice may not be removed or altered from any source distribution.
57
58--------------------------------------------------------------------------------
59cgltf
60--------------------------------------------------------------------------------
61
62Copyright (c) 2018-2021 Johannes Kuhlmann
63
64Permission is hereby granted, free of charge, to any person obtaining a copy of
65this software and associated documentation files (the "Software"), to deal in
66the Software without restriction, including without limitation the rights to
67use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
68the Software, and to permit persons to whom the Software is furnished to do so,
69subject to the following conditions:
70
71The above copyright notice and this permission notice shall be included in all
72copies or substantial portions of the Software.
73
74THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
75IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
76FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
77COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
78IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
79CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
diff --git a/contrib/cgltf-tangents/MikkTSpace/README.md b/contrib/cgltf-tangents/MikkTSpace/README.md
new file mode 100644
index 0000000..9fda155
--- /dev/null
+++ b/contrib/cgltf-tangents/MikkTSpace/README.md
@@ -0,0 +1,4 @@
1# MikkTSpace
2A common standard for tangent space used in baking tools to produce normal maps.
3
4More information can be found at http://www.mikktspace.com/.
diff --git a/contrib/cgltf-tangents/MikkTSpace/mikktspace.c b/contrib/cgltf-tangents/MikkTSpace/mikktspace.c
new file mode 100644
index 0000000..0342ae0
--- /dev/null
+++ b/contrib/cgltf-tangents/MikkTSpace/mikktspace.c
@@ -0,0 +1,1899 @@
1/** \file mikktspace/mikktspace.c
2 * \ingroup mikktspace
3 */
4/**
5 * Copyright (C) 2011 by Morten S. Mikkelsen
6 *
7 * This software is provided 'as-is', without any express or implied
8 * warranty. In no event will the authors be held liable for any damages
9 * arising from the use of this software.
10 *
11 * Permission is granted to anyone to use this software for any purpose,
12 * including commercial applications, and to alter it and redistribute it
13 * freely, subject to the following restrictions:
14 *
15 * 1. The origin of this software must not be misrepresented; you must not
16 * claim that you wrote the original software. If you use this software
17 * in a product, an acknowledgment in the product documentation would be
18 * appreciated but is not required.
19 * 2. Altered source versions must be plainly marked as such, and must not be
20 * misrepresented as being the original software.
21 * 3. This notice may not be removed or altered from any source distribution.
22 */
23
24#include <assert.h>
25#include <stdio.h>
26#include <math.h>
27#include <string.h>
28#include <float.h>
29#include <stdlib.h>
30
31#include "mikktspace.h"
32
33#define TFALSE 0
34#define TTRUE 1
35
36#ifndef M_PI
37#define M_PI 3.1415926535897932384626433832795
38#endif
39
40#define INTERNAL_RND_SORT_SEED 39871946
41
42// internal structure
43typedef struct {
44 float x, y, z;
45} SVec3;
46
47static tbool veq( const SVec3 v1, const SVec3 v2 )
48{
49 return (v1.x == v2.x) && (v1.y == v2.y) && (v1.z == v2.z);
50}
51
52static SVec3 vadd( const SVec3 v1, const SVec3 v2 )
53{
54 SVec3 vRes;
55
56 vRes.x = v1.x + v2.x;
57 vRes.y = v1.y + v2.y;
58 vRes.z = v1.z + v2.z;
59
60 return vRes;
61}
62
63
64static SVec3 vsub( const SVec3 v1, const SVec3 v2 )
65{
66 SVec3 vRes;
67
68 vRes.x = v1.x - v2.x;
69 vRes.y = v1.y - v2.y;
70 vRes.z = v1.z - v2.z;
71
72 return vRes;
73}
74
75static SVec3 vscale(const float fS, const SVec3 v)
76{
77 SVec3 vRes;
78
79 vRes.x = fS * v.x;
80 vRes.y = fS * v.y;
81 vRes.z = fS * v.z;
82
83 return vRes;
84}
85
86static float LengthSquared( const SVec3 v )
87{
88 return v.x*v.x + v.y*v.y + v.z*v.z;
89}
90
91static float Length( const SVec3 v )
92{
93 return sqrtf(LengthSquared(v));
94}
95
96static SVec3 Normalize( const SVec3 v )
97{
98 return vscale(1 / Length(v), v);
99}
100
101static float vdot( const SVec3 v1, const SVec3 v2)
102{
103 return v1.x*v2.x + v1.y*v2.y + v1.z*v2.z;
104}
105
106
107static tbool NotZero(const float fX)
108{
109 // could possibly use FLT_EPSILON instead
110 return fabsf(fX) > FLT_MIN;
111}
112
113static tbool VNotZero(const SVec3 v)
114{
115 // might change this to an epsilon based test
116 return NotZero(v.x) || NotZero(v.y) || NotZero(v.z);
117}
118
119
120
121typedef struct {
122 int iNrFaces;
123 int * pTriMembers;
124} SSubGroup;
125
126typedef struct {
127 int iNrFaces;
128 int * pFaceIndices;
129 int iVertexRepresentitive;
130 tbool bOrientPreservering;
131} SGroup;
132
133//
134#define MARK_DEGENERATE 1
135#define QUAD_ONE_DEGEN_TRI 2
136#define GROUP_WITH_ANY 4
137#define ORIENT_PRESERVING 8
138
139
140
141typedef struct {
142 int FaceNeighbors[3];
143 SGroup * AssignedGroup[3];
144
145 // normalized first order face derivatives
146 SVec3 vOs, vOt;
147 float fMagS, fMagT; // original magnitudes
148
149 // determines if the current and the next triangle are a quad.
150 int iOrgFaceNumber;
151 int iFlag, iTSpacesOffs;
152 unsigned char vert_num[4];
153} STriInfo;
154
155typedef struct {
156 SVec3 vOs;
157 float fMagS;
158 SVec3 vOt;
159 float fMagT;
160 int iCounter; // this is to average back into quads.
161 tbool bOrient;
162} STSpace;
163
164static int GenerateInitialVerticesIndexList(STriInfo pTriInfos[], int piTriList_out[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn);
165static void GenerateSharedVerticesIndexList(int piTriList_in_and_out[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn);
166static void InitTriInfo(STriInfo pTriInfos[], const int piTriListIn[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn);
167static int Build4RuleGroups(STriInfo pTriInfos[], SGroup pGroups[], int piGroupTrianglesBuffer[], const int piTriListIn[], const int iNrTrianglesIn);
168static tbool GenerateTSpaces(STSpace psTspace[], const STriInfo pTriInfos[], const SGroup pGroups[],
169 const int iNrActiveGroups, const int piTriListIn[], const float fThresCos,
170 const SMikkTSpaceContext * pContext);
171
172static int MakeIndex(const int iFace, const int iVert)
173{
174 assert(iVert>=0 && iVert<4 && iFace>=0);
175 return (iFace<<2) | (iVert&0x3);
176}
177
178static void IndexToData(int * piFace, int * piVert, const int iIndexIn)
179{
180 piVert[0] = iIndexIn&0x3;
181 piFace[0] = iIndexIn>>2;
182}
183
184static STSpace AvgTSpace(const STSpace * pTS0, const STSpace * pTS1)
185{
186 STSpace ts_res;
187
188 // this if is important. Due to floating point precision
189 // averaging when ts0==ts1 will cause a slight difference
190 // which results in tangent space splits later on
191 if (pTS0->fMagS==pTS1->fMagS && pTS0->fMagT==pTS1->fMagT &&
192 veq(pTS0->vOs,pTS1->vOs) && veq(pTS0->vOt, pTS1->vOt))
193 {
194 ts_res.fMagS = pTS0->fMagS;
195 ts_res.fMagT = pTS0->fMagT;
196 ts_res.vOs = pTS0->vOs;
197 ts_res.vOt = pTS0->vOt;
198 }
199 else
200 {
201 ts_res.fMagS = 0.5f*(pTS0->fMagS+pTS1->fMagS);
202 ts_res.fMagT = 0.5f*(pTS0->fMagT+pTS1->fMagT);
203 ts_res.vOs = vadd(pTS0->vOs,pTS1->vOs);
204 ts_res.vOt = vadd(pTS0->vOt,pTS1->vOt);
205 if ( VNotZero(ts_res.vOs) ) ts_res.vOs = Normalize(ts_res.vOs);
206 if ( VNotZero(ts_res.vOt) ) ts_res.vOt = Normalize(ts_res.vOt);
207 }
208
209 return ts_res;
210}
211
212
213
214static SVec3 GetPosition(const SMikkTSpaceContext * pContext, const int index);
215static SVec3 GetNormal(const SMikkTSpaceContext * pContext, const int index);
216static SVec3 GetTexCoord(const SMikkTSpaceContext * pContext, const int index);
217
218
219// degen triangles
220static void DegenPrologue(STriInfo pTriInfos[], int piTriList_out[], const int iNrTrianglesIn, const int iTotTris);
221static void DegenEpilogue(STSpace psTspace[], STriInfo pTriInfos[], int piTriListIn[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn, const int iTotTris);
222
223
224tbool genTangSpaceDefault(const SMikkTSpaceContext * pContext)
225{
226 return genTangSpace(pContext, 180.0f);
227}
228
229tbool genTangSpace(const SMikkTSpaceContext * pContext, const float fAngularThreshold)
230{
231 // count nr_triangles
232 int * piTriListIn = NULL, * piGroupTrianglesBuffer = NULL;
233 STriInfo * pTriInfos = NULL;
234 SGroup * pGroups = NULL;
235 STSpace * psTspace = NULL;
236 int iNrTrianglesIn = 0, f=0, t=0, i=0;
237 int iNrTSPaces = 0, iTotTris = 0, iDegenTriangles = 0, iNrMaxGroups = 0;
238 int iNrActiveGroups = 0, index = 0;
239 const int iNrFaces = pContext->m_pInterface->m_getNumFaces(pContext);
240 tbool bRes = TFALSE;
241 const float fThresCos = (float) cos((fAngularThreshold*(float)M_PI)/180.0f);
242
243 // verify all call-backs have been set
244 if ( pContext->m_pInterface->m_getNumFaces==NULL ||
245 pContext->m_pInterface->m_getNumVerticesOfFace==NULL ||
246 pContext->m_pInterface->m_getPosition==NULL ||
247 pContext->m_pInterface->m_getNormal==NULL ||
248 pContext->m_pInterface->m_getTexCoord==NULL )
249 return TFALSE;
250
251 // count triangles on supported faces
252 for (f=0; f<iNrFaces; f++)
253 {
254 const int verts = pContext->m_pInterface->m_getNumVerticesOfFace(pContext, f);
255 if (verts==3) ++iNrTrianglesIn;
256 else if (verts==4) iNrTrianglesIn += 2;
257 }
258 if (iNrTrianglesIn<=0) return TFALSE;
259
260 // allocate memory for an index list
261 piTriListIn = (int *) malloc(sizeof(int)*3*iNrTrianglesIn);
262 pTriInfos = (STriInfo *) malloc(sizeof(STriInfo)*iNrTrianglesIn);
263 if (piTriListIn==NULL || pTriInfos==NULL)
264 {
265 if (piTriListIn!=NULL) free(piTriListIn);
266 if (pTriInfos!=NULL) free(pTriInfos);
267 return TFALSE;
268 }
269
270 // make an initial triangle --> face index list
271 iNrTSPaces = GenerateInitialVerticesIndexList(pTriInfos, piTriListIn, pContext, iNrTrianglesIn);
272
273 // make a welded index list of identical positions and attributes (pos, norm, texc)
274 //printf("gen welded index list begin\n");
275 GenerateSharedVerticesIndexList(piTriListIn, pContext, iNrTrianglesIn);
276 //printf("gen welded index list end\n");
277
278 // Mark all degenerate triangles
279 iTotTris = iNrTrianglesIn;
280 iDegenTriangles = 0;
281 for (t=0; t<iTotTris; t++)
282 {
283 const int i0 = piTriListIn[t*3+0];
284 const int i1 = piTriListIn[t*3+1];
285 const int i2 = piTriListIn[t*3+2];
286 const SVec3 p0 = GetPosition(pContext, i0);
287 const SVec3 p1 = GetPosition(pContext, i1);
288 const SVec3 p2 = GetPosition(pContext, i2);
289 if (veq(p0,p1) || veq(p0,p2) || veq(p1,p2)) // degenerate
290 {
291 pTriInfos[t].iFlag |= MARK_DEGENERATE;
292 ++iDegenTriangles;
293 }
294 }
295 iNrTrianglesIn = iTotTris - iDegenTriangles;
296
297 // mark all triangle pairs that belong to a quad with only one
298 // good triangle. These need special treatment in DegenEpilogue().
299 // Additionally, move all good triangles to the start of
300 // pTriInfos[] and piTriListIn[] without changing order and
301 // put the degenerate triangles last.
302 DegenPrologue(pTriInfos, piTriListIn, iNrTrianglesIn, iTotTris);
303
304
305 // evaluate triangle level attributes and neighbor list
306 //printf("gen neighbors list begin\n");
307 InitTriInfo(pTriInfos, piTriListIn, pContext, iNrTrianglesIn);
308 //printf("gen neighbors list end\n");
309
310
311 // based on the 4 rules, identify groups based on connectivity
312 iNrMaxGroups = iNrTrianglesIn*3;
313 pGroups = (SGroup *) malloc(sizeof(SGroup)*iNrMaxGroups);
314 piGroupTrianglesBuffer = (int *) malloc(sizeof(int)*iNrTrianglesIn*3);
315 if (pGroups==NULL || piGroupTrianglesBuffer==NULL)
316 {
317 if (pGroups!=NULL) free(pGroups);
318 if (piGroupTrianglesBuffer!=NULL) free(piGroupTrianglesBuffer);
319 free(piTriListIn);
320 free(pTriInfos);
321 return TFALSE;
322 }
323 //printf("gen 4rule groups begin\n");
324 iNrActiveGroups =
325 Build4RuleGroups(pTriInfos, pGroups, piGroupTrianglesBuffer, piTriListIn, iNrTrianglesIn);
326 //printf("gen 4rule groups end\n");
327
328 //
329
330 psTspace = (STSpace *) malloc(sizeof(STSpace)*iNrTSPaces);
331 if (psTspace==NULL)
332 {
333 free(piTriListIn);
334 free(pTriInfos);
335 free(pGroups);
336 free(piGroupTrianglesBuffer);
337 return TFALSE;
338 }
339 memset(psTspace, 0, sizeof(STSpace)*iNrTSPaces);
340 for (t=0; t<iNrTSPaces; t++)
341 {
342 psTspace[t].vOs.x=1.0f; psTspace[t].vOs.y=0.0f; psTspace[t].vOs.z=0.0f; psTspace[t].fMagS = 1.0f;
343 psTspace[t].vOt.x=0.0f; psTspace[t].vOt.y=1.0f; psTspace[t].vOt.z=0.0f; psTspace[t].fMagT = 1.0f;
344 }
345
346 // make tspaces, each group is split up into subgroups if necessary
347 // based on fAngularThreshold. Finally a tangent space is made for
348 // every resulting subgroup
349 //printf("gen tspaces begin\n");
350 bRes = GenerateTSpaces(psTspace, pTriInfos, pGroups, iNrActiveGroups, piTriListIn, fThresCos, pContext);
351 //printf("gen tspaces end\n");
352
353 // clean up
354 free(pGroups);
355 free(piGroupTrianglesBuffer);
356
357 if (!bRes) // if an allocation in GenerateTSpaces() failed
358 {
359 // clean up and return false
360 free(pTriInfos); free(piTriListIn); free(psTspace);
361 return TFALSE;
362 }
363
364
365 // degenerate quads with one good triangle will be fixed by copying a space from
366 // the good triangle to the coinciding vertex.
367 // all other degenerate triangles will just copy a space from any good triangle
368 // with the same welded index in piTriListIn[].
369 DegenEpilogue(psTspace, pTriInfos, piTriListIn, pContext, iNrTrianglesIn, iTotTris);
370
371 free(pTriInfos); free(piTriListIn);
372
373 index = 0;
374 for (f=0; f<iNrFaces; f++)
375 {
376 const int verts = pContext->m_pInterface->m_getNumVerticesOfFace(pContext, f);
377 if (verts!=3 && verts!=4) continue;
378
379
380 // I've decided to let degenerate triangles and group-with-anythings
381 // vary between left/right hand coordinate systems at the vertices.
382 // All healthy triangles on the other hand are built to always be either or.
383
384 /*// force the coordinate system orientation to be uniform for every face.
385 // (this is already the case for good triangles but not for
386 // degenerate ones and those with bGroupWithAnything==true)
387 bool bOrient = psTspace[index].bOrient;
388 if (psTspace[index].iCounter == 0) // tspace was not derived from a group
389 {
390 // look for a space created in GenerateTSpaces() by iCounter>0
391 bool bNotFound = true;
392 int i=1;
393 while (i<verts && bNotFound)
394 {
395 if (psTspace[index+i].iCounter > 0) bNotFound=false;
396 else ++i;
397 }
398 if (!bNotFound) bOrient = psTspace[index+i].bOrient;
399 }*/
400
401 // set data
402 for (i=0; i<verts; i++)
403 {
404 const STSpace * pTSpace = &psTspace[index];
405 float tang[] = {pTSpace->vOs.x, pTSpace->vOs.y, pTSpace->vOs.z};
406 float bitang[] = {pTSpace->vOt.x, pTSpace->vOt.y, pTSpace->vOt.z};
407 if (pContext->m_pInterface->m_setTSpace!=NULL)
408 pContext->m_pInterface->m_setTSpace(pContext, tang, bitang, pTSpace->fMagS, pTSpace->fMagT, pTSpace->bOrient, f, i);
409 if (pContext->m_pInterface->m_setTSpaceBasic!=NULL)
410 pContext->m_pInterface->m_setTSpaceBasic(pContext, tang, pTSpace->bOrient==TTRUE ? 1.0f : (-1.0f), f, i);
411
412 ++index;
413 }
414 }
415
416 free(psTspace);
417
418
419 return TTRUE;
420}
421
422///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
423
424typedef struct {
425 float vert[3];
426 int index;
427} STmpVert;
428
429static const int g_iCells = 2048;
430
431#ifdef _MSC_VER
432# define NOINLINE __declspec(noinline)
433#else
434# define NOINLINE __attribute__ ((noinline))
435#endif
436
437// it is IMPORTANT that this function is called to evaluate the hash since
438// inlining could potentially reorder instructions and generate different
439// results for the same effective input value fVal.
440static NOINLINE int FindGridCell(const float fMin, const float fMax, const float fVal)
441{
442 const float fIndex = g_iCells * ((fVal-fMin)/(fMax-fMin));
443 const int iIndex = (int)fIndex;
444 return iIndex < g_iCells ? (iIndex >= 0 ? iIndex : 0) : (g_iCells - 1);
445}
446
447static void MergeVertsFast(int piTriList_in_and_out[], STmpVert pTmpVert[], const SMikkTSpaceContext * pContext, const int iL_in, const int iR_in);
448static void MergeVertsSlow(int piTriList_in_and_out[], const SMikkTSpaceContext * pContext, const int pTable[], const int iEntries);
449static void GenerateSharedVerticesIndexListSlow(int piTriList_in_and_out[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn);
450
451static void GenerateSharedVerticesIndexList(int piTriList_in_and_out[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn)
452{
453
454 // Generate bounding box
455 int * piHashTable=NULL, * piHashCount=NULL, * piHashOffsets=NULL, * piHashCount2=NULL;
456 STmpVert * pTmpVert = NULL;
457 int i=0, iChannel=0, k=0, e=0;
458 int iMaxCount=0;
459 SVec3 vMin = GetPosition(pContext, 0), vMax = vMin, vDim;
460 float fMin, fMax;
461 for (i=1; i<(iNrTrianglesIn*3); i++)
462 {
463 const int index = piTriList_in_and_out[i];
464
465 const SVec3 vP = GetPosition(pContext, index);
466 if (vMin.x > vP.x) vMin.x = vP.x;
467 else if (vMax.x < vP.x) vMax.x = vP.x;
468 if (vMin.y > vP.y) vMin.y = vP.y;
469 else if (vMax.y < vP.y) vMax.y = vP.y;
470 if (vMin.z > vP.z) vMin.z = vP.z;
471 else if (vMax.z < vP.z) vMax.z = vP.z;
472 }
473
474 vDim = vsub(vMax,vMin);
475 iChannel = 0;
476 fMin = vMin.x; fMax=vMax.x;
477 if (vDim.y>vDim.x && vDim.y>vDim.z)
478 {
479 iChannel=1;
480 fMin = vMin.y;
481 fMax = vMax.y;
482 }
483 else if (vDim.z>vDim.x)
484 {
485 iChannel=2;
486 fMin = vMin.z;
487 fMax = vMax.z;
488 }
489
490 // make allocations
491 piHashTable = (int *) malloc(sizeof(int)*iNrTrianglesIn*3);
492 piHashCount = (int *) malloc(sizeof(int)*g_iCells);
493 piHashOffsets = (int *) malloc(sizeof(int)*g_iCells);
494 piHashCount2 = (int *) malloc(sizeof(int)*g_iCells);
495
496 if (piHashTable==NULL || piHashCount==NULL || piHashOffsets==NULL || piHashCount2==NULL)
497 {
498 if (piHashTable!=NULL) free(piHashTable);
499 if (piHashCount!=NULL) free(piHashCount);
500 if (piHashOffsets!=NULL) free(piHashOffsets);
501 if (piHashCount2!=NULL) free(piHashCount2);
502 GenerateSharedVerticesIndexListSlow(piTriList_in_and_out, pContext, iNrTrianglesIn);
503 return;
504 }
505 memset(piHashCount, 0, sizeof(int)*g_iCells);
506 memset(piHashCount2, 0, sizeof(int)*g_iCells);
507
508 // count amount of elements in each cell unit
509 for (i=0; i<(iNrTrianglesIn*3); i++)
510 {
511 const int index = piTriList_in_and_out[i];
512 const SVec3 vP = GetPosition(pContext, index);
513 const float fVal = iChannel==0 ? vP.x : (iChannel==1 ? vP.y : vP.z);
514 const int iCell = FindGridCell(fMin, fMax, fVal);
515 ++piHashCount[iCell];
516 }
517
518 // evaluate start index of each cell.
519 piHashOffsets[0]=0;
520 for (k=1; k<g_iCells; k++)
521 piHashOffsets[k]=piHashOffsets[k-1]+piHashCount[k-1];
522
523 // insert vertices
524 for (i=0; i<(iNrTrianglesIn*3); i++)
525 {
526 const int index = piTriList_in_and_out[i];
527 const SVec3 vP = GetPosition(pContext, index);
528 const float fVal = iChannel==0 ? vP.x : (iChannel==1 ? vP.y : vP.z);
529 const int iCell = FindGridCell(fMin, fMax, fVal);
530 int * pTable = NULL;
531
532 assert(piHashCount2[iCell]<piHashCount[iCell]);
533 pTable = &piHashTable[piHashOffsets[iCell]];
534 pTable[piHashCount2[iCell]] = i; // vertex i has been inserted.
535 ++piHashCount2[iCell];
536 }
537 for (k=0; k<g_iCells; k++)
538 assert(piHashCount2[k] == piHashCount[k]); // verify the count
539 free(piHashCount2);
540
541 // find maximum amount of entries in any hash entry
542 iMaxCount = piHashCount[0];
543 for (k=1; k<g_iCells; k++)
544 if (iMaxCount<piHashCount[k])
545 iMaxCount=piHashCount[k];
546 pTmpVert = (STmpVert *) malloc(sizeof(STmpVert)*iMaxCount);
547
548
549 // complete the merge
550 for (k=0; k<g_iCells; k++)
551 {
552 // extract table of cell k and amount of entries in it
553 int * pTable = &piHashTable[piHashOffsets[k]];
554 const int iEntries = piHashCount[k];
555 if (iEntries < 2) continue;
556
557 if (pTmpVert!=NULL)
558 {
559 for (e=0; e<iEntries; e++)
560 {
561 int i = pTable[e];
562 const SVec3 vP = GetPosition(pContext, piTriList_in_and_out[i]);
563 pTmpVert[e].vert[0] = vP.x; pTmpVert[e].vert[1] = vP.y;
564 pTmpVert[e].vert[2] = vP.z; pTmpVert[e].index = i;
565 }
566 MergeVertsFast(piTriList_in_and_out, pTmpVert, pContext, 0, iEntries-1);
567 }
568 else
569 MergeVertsSlow(piTriList_in_and_out, pContext, pTable, iEntries);
570 }
571
572 if (pTmpVert!=NULL) { free(pTmpVert); }
573 free(piHashTable);
574 free(piHashCount);
575 free(piHashOffsets);
576}
577
578static void MergeVertsFast(int piTriList_in_and_out[], STmpVert pTmpVert[], const SMikkTSpaceContext * pContext, const int iL_in, const int iR_in)
579{
580 // make bbox
581 int c=0, l=0, channel=0;
582 float fvMin[3], fvMax[3];
583 float dx=0, dy=0, dz=0, fSep=0;
584 for (c=0; c<3; c++)
585 { fvMin[c]=pTmpVert[iL_in].vert[c]; fvMax[c]=fvMin[c]; }
586 for (l=(iL_in+1); l<=iR_in; l++) {
587 for (c=0; c<3; c++) {
588 if (fvMin[c]>pTmpVert[l].vert[c]) fvMin[c]=pTmpVert[l].vert[c];
589 if (fvMax[c]<pTmpVert[l].vert[c]) fvMax[c]=pTmpVert[l].vert[c];
590 }
591 }
592
593 dx = fvMax[0]-fvMin[0];
594 dy = fvMax[1]-fvMin[1];
595 dz = fvMax[2]-fvMin[2];
596
597 channel = 0;
598 if (dy>dx && dy>dz) channel=1;
599 else if (dz>dx) channel=2;
600
601 fSep = 0.5f*(fvMax[channel]+fvMin[channel]);
602
603 // stop if all vertices are NaNs
604 if (!isfinite(fSep))
605 return;
606
607 // terminate recursion when the separation/average value
608 // is no longer strictly between fMin and fMax values.
609 if (fSep>=fvMax[channel] || fSep<=fvMin[channel])
610 {
611 // complete the weld
612 for (l=iL_in; l<=iR_in; l++)
613 {
614 int i = pTmpVert[l].index;
615 const int index = piTriList_in_and_out[i];
616 const SVec3 vP = GetPosition(pContext, index);
617 const SVec3 vN = GetNormal(pContext, index);
618 const SVec3 vT = GetTexCoord(pContext, index);
619
620 tbool bNotFound = TTRUE;
621 int l2=iL_in, i2rec=-1;
622 while (l2<l && bNotFound)
623 {
624 const int i2 = pTmpVert[l2].index;
625 const int index2 = piTriList_in_and_out[i2];
626 const SVec3 vP2 = GetPosition(pContext, index2);
627 const SVec3 vN2 = GetNormal(pContext, index2);
628 const SVec3 vT2 = GetTexCoord(pContext, index2);
629 i2rec=i2;
630
631 //if (vP==vP2 && vN==vN2 && vT==vT2)
632 if (vP.x==vP2.x && vP.y==vP2.y && vP.z==vP2.z &&
633 vN.x==vN2.x && vN.y==vN2.y && vN.z==vN2.z &&
634 vT.x==vT2.x && vT.y==vT2.y && vT.z==vT2.z)
635 bNotFound = TFALSE;
636 else
637 ++l2;
638 }
639
640 // merge if previously found
641 if (!bNotFound)
642 piTriList_in_and_out[i] = piTriList_in_and_out[i2rec];
643 }
644 }
645 else
646 {
647 int iL=iL_in, iR=iR_in;
648 assert((iR_in-iL_in)>0); // at least 2 entries
649
650 // separate (by fSep) all points between iL_in and iR_in in pTmpVert[]
651 while (iL < iR)
652 {
653 tbool bReadyLeftSwap = TFALSE, bReadyRightSwap = TFALSE;
654 while ((!bReadyLeftSwap) && iL<iR)
655 {
656 assert(iL>=iL_in && iL<=iR_in);
657 bReadyLeftSwap = !(pTmpVert[iL].vert[channel]<fSep);
658 if (!bReadyLeftSwap) ++iL;
659 }
660 while ((!bReadyRightSwap) && iL<iR)
661 {
662 assert(iR>=iL_in && iR<=iR_in);
663 bReadyRightSwap = pTmpVert[iR].vert[channel]<fSep;
664 if (!bReadyRightSwap) --iR;
665 }
666 assert( (iL<iR) || !(bReadyLeftSwap && bReadyRightSwap) );
667
668 if (bReadyLeftSwap && bReadyRightSwap)
669 {
670 const STmpVert sTmp = pTmpVert[iL];
671 assert(iL<iR);
672 pTmpVert[iL] = pTmpVert[iR];
673 pTmpVert[iR] = sTmp;
674 ++iL; --iR;
675 }
676 }
677
678 assert(iL==(iR+1) || (iL==iR));
679 if (iL==iR)
680 {
681 const tbool bReadyRightSwap = pTmpVert[iR].vert[channel]<fSep;
682 if (bReadyRightSwap) ++iL;
683 else --iR;
684 }
685
686 // only need to weld when there is more than 1 instance of the (x,y,z)
687 if (iL_in < iR)
688 MergeVertsFast(piTriList_in_and_out, pTmpVert, pContext, iL_in, iR); // weld all left of fSep
689 if (iL < iR_in)
690 MergeVertsFast(piTriList_in_and_out, pTmpVert, pContext, iL, iR_in); // weld all right of (or equal to) fSep
691 }
692}
693
694static void MergeVertsSlow(int piTriList_in_and_out[], const SMikkTSpaceContext * pContext, const int pTable[], const int iEntries)
695{
696 // this can be optimized further using a tree structure or more hashing.
697 int e=0;
698 for (e=0; e<iEntries; e++)
699 {
700 int i = pTable[e];
701 const int index = piTriList_in_and_out[i];
702 const SVec3 vP = GetPosition(pContext, index);
703 const SVec3 vN = GetNormal(pContext, index);
704 const SVec3 vT = GetTexCoord(pContext, index);
705
706 tbool bNotFound = TTRUE;
707 int e2=0, i2rec=-1;
708 while (e2<e && bNotFound)
709 {
710 const int i2 = pTable[e2];
711 const int index2 = piTriList_in_and_out[i2];
712 const SVec3 vP2 = GetPosition(pContext, index2);
713 const SVec3 vN2 = GetNormal(pContext, index2);
714 const SVec3 vT2 = GetTexCoord(pContext, index2);
715 i2rec = i2;
716
717 if (veq(vP,vP2) && veq(vN,vN2) && veq(vT,vT2))
718 bNotFound = TFALSE;
719 else
720 ++e2;
721 }
722
723 // merge if previously found
724 if (!bNotFound)
725 piTriList_in_and_out[i] = piTriList_in_and_out[i2rec];
726 }
727}
728
729static void GenerateSharedVerticesIndexListSlow(int piTriList_in_and_out[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn)
730{
731 int iNumUniqueVerts = 0, t=0, i=0;
732 for (t=0; t<iNrTrianglesIn; t++)
733 {
734 for (i=0; i<3; i++)
735 {
736 const int offs = t*3 + i;
737 const int index = piTriList_in_and_out[offs];
738
739 const SVec3 vP = GetPosition(pContext, index);
740 const SVec3 vN = GetNormal(pContext, index);
741 const SVec3 vT = GetTexCoord(pContext, index);
742
743 tbool bFound = TFALSE;
744 int t2=0, index2rec=-1;
745 while (!bFound && t2<=t)
746 {
747 int j=0;
748 while (!bFound && j<3)
749 {
750 const int index2 = piTriList_in_and_out[t2*3 + j];
751 const SVec3 vP2 = GetPosition(pContext, index2);
752 const SVec3 vN2 = GetNormal(pContext, index2);
753 const SVec3 vT2 = GetTexCoord(pContext, index2);
754
755 if (veq(vP,vP2) && veq(vN,vN2) && veq(vT,vT2))
756 bFound = TTRUE;
757 else
758 ++j;
759 }
760 if (!bFound) ++t2;
761 }
762
763 assert(bFound);
764 // if we found our own
765 if (index2rec == index) { ++iNumUniqueVerts; }
766
767 piTriList_in_and_out[offs] = index2rec;
768 }
769 }
770}
771
772static int GenerateInitialVerticesIndexList(STriInfo pTriInfos[], int piTriList_out[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn)
773{
774 int iTSpacesOffs = 0, f=0, t=0;
775 int iDstTriIndex = 0;
776 for (f=0; f<pContext->m_pInterface->m_getNumFaces(pContext); f++)
777 {
778 const int verts = pContext->m_pInterface->m_getNumVerticesOfFace(pContext, f);
779 if (verts!=3 && verts!=4) continue;
780
781 pTriInfos[iDstTriIndex].iOrgFaceNumber = f;
782 pTriInfos[iDstTriIndex].iTSpacesOffs = iTSpacesOffs;
783
784 if (verts==3)
785 {
786 unsigned char * pVerts = pTriInfos[iDstTriIndex].vert_num;
787 pVerts[0]=0; pVerts[1]=1; pVerts[2]=2;
788 piTriList_out[iDstTriIndex*3+0] = MakeIndex(f, 0);
789 piTriList_out[iDstTriIndex*3+1] = MakeIndex(f, 1);
790 piTriList_out[iDstTriIndex*3+2] = MakeIndex(f, 2);
791 ++iDstTriIndex; // next
792 }
793 else
794 {
795 {
796 pTriInfos[iDstTriIndex+1].iOrgFaceNumber = f;
797 pTriInfos[iDstTriIndex+1].iTSpacesOffs = iTSpacesOffs;
798 }
799
800 {
801 // need an order independent way to evaluate
802 // tspace on quads. This is done by splitting
803 // along the shortest diagonal.
804 const int i0 = MakeIndex(f, 0);
805 const int i1 = MakeIndex(f, 1);
806 const int i2 = MakeIndex(f, 2);
807 const int i3 = MakeIndex(f, 3);
808 const SVec3 T0 = GetTexCoord(pContext, i0);
809 const SVec3 T1 = GetTexCoord(pContext, i1);
810 const SVec3 T2 = GetTexCoord(pContext, i2);
811 const SVec3 T3 = GetTexCoord(pContext, i3);
812 const float distSQ_02 = LengthSquared(vsub(T2,T0));
813 const float distSQ_13 = LengthSquared(vsub(T3,T1));
814 tbool bQuadDiagIs_02;
815 if (distSQ_02<distSQ_13)
816 bQuadDiagIs_02 = TTRUE;
817 else if (distSQ_13<distSQ_02)
818 bQuadDiagIs_02 = TFALSE;
819 else
820 {
821 const SVec3 P0 = GetPosition(pContext, i0);
822 const SVec3 P1 = GetPosition(pContext, i1);
823 const SVec3 P2 = GetPosition(pContext, i2);
824 const SVec3 P3 = GetPosition(pContext, i3);
825 const float distSQ_02 = LengthSquared(vsub(P2,P0));
826 const float distSQ_13 = LengthSquared(vsub(P3,P1));
827
828 bQuadDiagIs_02 = distSQ_13<distSQ_02 ? TFALSE : TTRUE;
829 }
830
831 if (bQuadDiagIs_02)
832 {
833 {
834 unsigned char * pVerts_A = pTriInfos[iDstTriIndex].vert_num;
835 pVerts_A[0]=0; pVerts_A[1]=1; pVerts_A[2]=2;
836 }
837 piTriList_out[iDstTriIndex*3+0] = i0;
838 piTriList_out[iDstTriIndex*3+1] = i1;
839 piTriList_out[iDstTriIndex*3+2] = i2;
840 ++iDstTriIndex; // next
841 {
842 unsigned char * pVerts_B = pTriInfos[iDstTriIndex].vert_num;
843 pVerts_B[0]=0; pVerts_B[1]=2; pVerts_B[2]=3;
844 }
845 piTriList_out[iDstTriIndex*3+0] = i0;
846 piTriList_out[iDstTriIndex*3+1] = i2;
847 piTriList_out[iDstTriIndex*3+2] = i3;
848 ++iDstTriIndex; // next
849 }
850 else
851 {
852 {
853 unsigned char * pVerts_A = pTriInfos[iDstTriIndex].vert_num;
854 pVerts_A[0]=0; pVerts_A[1]=1; pVerts_A[2]=3;
855 }
856 piTriList_out[iDstTriIndex*3+0] = i0;
857 piTriList_out[iDstTriIndex*3+1] = i1;
858 piTriList_out[iDstTriIndex*3+2] = i3;
859 ++iDstTriIndex; // next
860 {
861 unsigned char * pVerts_B = pTriInfos[iDstTriIndex].vert_num;
862 pVerts_B[0]=1; pVerts_B[1]=2; pVerts_B[2]=3;
863 }
864 piTriList_out[iDstTriIndex*3+0] = i1;
865 piTriList_out[iDstTriIndex*3+1] = i2;
866 piTriList_out[iDstTriIndex*3+2] = i3;
867 ++iDstTriIndex; // next
868 }
869 }
870 }
871
872 iTSpacesOffs += verts;
873 assert(iDstTriIndex<=iNrTrianglesIn);
874 }
875
876 for (t=0; t<iNrTrianglesIn; t++)
877 pTriInfos[t].iFlag = 0;
878
879 // return total amount of tspaces
880 return iTSpacesOffs;
881}
882
883static SVec3 GetPosition(const SMikkTSpaceContext * pContext, const int index)
884{
885 int iF, iI;
886 SVec3 res; float pos[3];
887 IndexToData(&iF, &iI, index);
888 pContext->m_pInterface->m_getPosition(pContext, pos, iF, iI);
889 res.x=pos[0]; res.y=pos[1]; res.z=pos[2];
890 return res;
891}
892
893static SVec3 GetNormal(const SMikkTSpaceContext * pContext, const int index)
894{
895 int iF, iI;
896 SVec3 res; float norm[3];
897 IndexToData(&iF, &iI, index);
898 pContext->m_pInterface->m_getNormal(pContext, norm, iF, iI);
899 res.x=norm[0]; res.y=norm[1]; res.z=norm[2];
900 return res;
901}
902
903static SVec3 GetTexCoord(const SMikkTSpaceContext * pContext, const int index)
904{
905 int iF, iI;
906 SVec3 res; float texc[2];
907 IndexToData(&iF, &iI, index);
908 pContext->m_pInterface->m_getTexCoord(pContext, texc, iF, iI);
909 res.x=texc[0]; res.y=texc[1]; res.z=1.0f;
910 return res;
911}
912
913/////////////////////////////////////////////////////////////////////////////////////////////////////
914/////////////////////////////////////////////////////////////////////////////////////////////////////
915
916typedef union {
917 struct
918 {
919 int i0, i1, f;
920 };
921 int array[3];
922} SEdge;
923
924static void BuildNeighborsFast(STriInfo pTriInfos[], SEdge * pEdges, const int piTriListIn[], const int iNrTrianglesIn);
925static void BuildNeighborsSlow(STriInfo pTriInfos[], const int piTriListIn[], const int iNrTrianglesIn);
926
927// returns the texture area times 2
928static float CalcTexArea(const SMikkTSpaceContext * pContext, const int indices[])
929{
930 const SVec3 t1 = GetTexCoord(pContext, indices[0]);
931 const SVec3 t2 = GetTexCoord(pContext, indices[1]);
932 const SVec3 t3 = GetTexCoord(pContext, indices[2]);
933
934 const float t21x = t2.x-t1.x;
935 const float t21y = t2.y-t1.y;
936 const float t31x = t3.x-t1.x;
937 const float t31y = t3.y-t1.y;
938
939 const float fSignedAreaSTx2 = t21x*t31y - t21y*t31x;
940
941 return fSignedAreaSTx2<0 ? (-fSignedAreaSTx2) : fSignedAreaSTx2;
942}
943
944static void InitTriInfo(STriInfo pTriInfos[], const int piTriListIn[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn)
945{
946 int f=0, i=0, t=0;
947 // pTriInfos[f].iFlag is cleared in GenerateInitialVerticesIndexList() which is called before this function.
948
949 // generate neighbor info list
950 for (f=0; f<iNrTrianglesIn; f++)
951 for (i=0; i<3; i++)
952 {
953 pTriInfos[f].FaceNeighbors[i] = -1;
954 pTriInfos[f].AssignedGroup[i] = NULL;
955
956 pTriInfos[f].vOs.x=0.0f; pTriInfos[f].vOs.y=0.0f; pTriInfos[f].vOs.z=0.0f;
957 pTriInfos[f].vOt.x=0.0f; pTriInfos[f].vOt.y=0.0f; pTriInfos[f].vOt.z=0.0f;
958 pTriInfos[f].fMagS = 0;
959 pTriInfos[f].fMagT = 0;
960
961 // assumed bad
962 pTriInfos[f].iFlag |= GROUP_WITH_ANY;
963 }
964
965 // evaluate first order derivatives
966 for (f=0; f<iNrTrianglesIn; f++)
967 {
968 // initial values
969 const SVec3 v1 = GetPosition(pContext, piTriListIn[f*3+0]);
970 const SVec3 v2 = GetPosition(pContext, piTriListIn[f*3+1]);
971 const SVec3 v3 = GetPosition(pContext, piTriListIn[f*3+2]);
972 const SVec3 t1 = GetTexCoord(pContext, piTriListIn[f*3+0]);
973 const SVec3 t2 = GetTexCoord(pContext, piTriListIn[f*3+1]);
974 const SVec3 t3 = GetTexCoord(pContext, piTriListIn[f*3+2]);
975
976 const float t21x = t2.x-t1.x;
977 const float t21y = t2.y-t1.y;
978 const float t31x = t3.x-t1.x;
979 const float t31y = t3.y-t1.y;
980 const SVec3 d1 = vsub(v2,v1);
981 const SVec3 d2 = vsub(v3,v1);
982
983 const float fSignedAreaSTx2 = t21x*t31y - t21y*t31x;
984 //assert(fSignedAreaSTx2!=0);
985 SVec3 vOs = vsub(vscale(t31y,d1), vscale(t21y,d2)); // eq 18
986 SVec3 vOt = vadd(vscale(-t31x,d1), vscale(t21x,d2)); // eq 19
987
988 pTriInfos[f].iFlag |= (fSignedAreaSTx2>0 ? ORIENT_PRESERVING : 0);
989
990 if ( NotZero(fSignedAreaSTx2) )
991 {
992 const float fAbsArea = fabsf(fSignedAreaSTx2);
993 const float fLenOs = Length(vOs);
994 const float fLenOt = Length(vOt);
995 const float fS = (pTriInfos[f].iFlag&ORIENT_PRESERVING)==0 ? (-1.0f) : 1.0f;
996 if ( NotZero(fLenOs) ) pTriInfos[f].vOs = vscale(fS/fLenOs, vOs);
997 if ( NotZero(fLenOt) ) pTriInfos[f].vOt = vscale(fS/fLenOt, vOt);
998
999 // evaluate magnitudes prior to normalization of vOs and vOt
1000 pTriInfos[f].fMagS = fLenOs / fAbsArea;
1001 pTriInfos[f].fMagT = fLenOt / fAbsArea;
1002
1003 // if this is a good triangle
1004 if ( NotZero(pTriInfos[f].fMagS) && NotZero(pTriInfos[f].fMagT))
1005 pTriInfos[f].iFlag &= (~GROUP_WITH_ANY);
1006 }
1007 }
1008
1009 // force otherwise healthy quads to a fixed orientation
1010 while (t<(iNrTrianglesIn-1))
1011 {
1012 const int iFO_a = pTriInfos[t].iOrgFaceNumber;
1013 const int iFO_b = pTriInfos[t+1].iOrgFaceNumber;
1014 if (iFO_a==iFO_b) // this is a quad
1015 {
1016 const tbool bIsDeg_a = (pTriInfos[t].iFlag&MARK_DEGENERATE)!=0 ? TTRUE : TFALSE;
1017 const tbool bIsDeg_b = (pTriInfos[t+1].iFlag&MARK_DEGENERATE)!=0 ? TTRUE : TFALSE;
1018
1019 // bad triangles should already have been removed by
1020 // DegenPrologue(), but just in case check bIsDeg_a and bIsDeg_a are false
1021 if ((bIsDeg_a||bIsDeg_b)==TFALSE)
1022 {
1023 const tbool bOrientA = (pTriInfos[t].iFlag&ORIENT_PRESERVING)!=0 ? TTRUE : TFALSE;
1024 const tbool bOrientB = (pTriInfos[t+1].iFlag&ORIENT_PRESERVING)!=0 ? TTRUE : TFALSE;
1025 // if this happens the quad has extremely bad mapping!!
1026 if (bOrientA!=bOrientB)
1027 {
1028 //printf("found quad with bad mapping\n");
1029 tbool bChooseOrientFirstTri = TFALSE;
1030 if ((pTriInfos[t+1].iFlag&GROUP_WITH_ANY)!=0) bChooseOrientFirstTri = TTRUE;
1031 else if ( CalcTexArea(pContext, &piTriListIn[t*3+0]) >= CalcTexArea(pContext, &piTriListIn[(t+1)*3+0]) )
1032 bChooseOrientFirstTri = TTRUE;
1033
1034 // force match
1035 {
1036 const int t0 = bChooseOrientFirstTri ? t : (t+1);
1037 const int t1 = bChooseOrientFirstTri ? (t+1) : t;
1038 pTriInfos[t1].iFlag &= (~ORIENT_PRESERVING); // clear first
1039 pTriInfos[t1].iFlag |= (pTriInfos[t0].iFlag&ORIENT_PRESERVING); // copy bit
1040 }
1041 }
1042 }
1043 t += 2;
1044 }
1045 else
1046 ++t;
1047 }
1048
1049 // match up edge pairs
1050 {
1051 SEdge * pEdges = (SEdge *) malloc(sizeof(SEdge)*iNrTrianglesIn*3);
1052 if (pEdges==NULL)
1053 BuildNeighborsSlow(pTriInfos, piTriListIn, iNrTrianglesIn);
1054 else
1055 {
1056 BuildNeighborsFast(pTriInfos, pEdges, piTriListIn, iNrTrianglesIn);
1057
1058 free(pEdges);
1059 }
1060 }
1061}
1062
1063/////////////////////////////////////////////////////////////////////////////////////////////////////
1064/////////////////////////////////////////////////////////////////////////////////////////////////////
1065
1066static tbool AssignRecur(const int piTriListIn[], STriInfo psTriInfos[], const int iMyTriIndex, SGroup * pGroup);
1067static void AddTriToGroup(SGroup * pGroup, const int iTriIndex);
1068
1069static int Build4RuleGroups(STriInfo pTriInfos[], SGroup pGroups[], int piGroupTrianglesBuffer[], const int piTriListIn[], const int iNrTrianglesIn)
1070{
1071 const int iNrMaxGroups = iNrTrianglesIn*3;
1072 int iNrActiveGroups = 0;
1073 int iOffset = 0, f=0, i=0;
1074 (void)iNrMaxGroups; /* quiet warnings in non debug mode */
1075 for (f=0; f<iNrTrianglesIn; f++)
1076 {
1077 for (i=0; i<3; i++)
1078 {
1079 // if not assigned to a group
1080 if ((pTriInfos[f].iFlag&GROUP_WITH_ANY)==0 && pTriInfos[f].AssignedGroup[i]==NULL)
1081 {
1082 tbool bOrPre;
1083 int neigh_indexL, neigh_indexR;
1084 const int vert_index = piTriListIn[f*3+i];
1085 assert(iNrActiveGroups<iNrMaxGroups);
1086 pTriInfos[f].AssignedGroup[i] = &pGroups[iNrActiveGroups];
1087 pTriInfos[f].AssignedGroup[i]->iVertexRepresentitive = vert_index;
1088 pTriInfos[f].AssignedGroup[i]->bOrientPreservering = (pTriInfos[f].iFlag&ORIENT_PRESERVING)!=0;
1089 pTriInfos[f].AssignedGroup[i]->iNrFaces = 0;
1090 pTriInfos[f].AssignedGroup[i]->pFaceIndices = &piGroupTrianglesBuffer[iOffset];
1091 ++iNrActiveGroups;
1092
1093 AddTriToGroup(pTriInfos[f].AssignedGroup[i], f);
1094 bOrPre = (pTriInfos[f].iFlag&ORIENT_PRESERVING)!=0 ? TTRUE : TFALSE;
1095 neigh_indexL = pTriInfos[f].FaceNeighbors[i];
1096 neigh_indexR = pTriInfos[f].FaceNeighbors[i>0?(i-1):2];
1097 if (neigh_indexL>=0) // neighbor
1098 {
1099 const tbool bAnswer =
1100 AssignRecur(piTriListIn, pTriInfos, neigh_indexL,
1101 pTriInfos[f].AssignedGroup[i] );
1102
1103 const tbool bOrPre2 = (pTriInfos[neigh_indexL].iFlag&ORIENT_PRESERVING)!=0 ? TTRUE : TFALSE;
1104 const tbool bDiff = bOrPre!=bOrPre2 ? TTRUE : TFALSE;
1105 assert(bAnswer || bDiff);
1106 (void)bAnswer, (void)bDiff; /* quiet warnings in non debug mode */
1107 }
1108 if (neigh_indexR>=0) // neighbor
1109 {
1110 const tbool bAnswer =
1111 AssignRecur(piTriListIn, pTriInfos, neigh_indexR,
1112 pTriInfos[f].AssignedGroup[i] );
1113
1114 const tbool bOrPre2 = (pTriInfos[neigh_indexR].iFlag&ORIENT_PRESERVING)!=0 ? TTRUE : TFALSE;
1115 const tbool bDiff = bOrPre!=bOrPre2 ? TTRUE : TFALSE;
1116 assert(bAnswer || bDiff);
1117 (void)bAnswer, (void)bDiff; /* quiet warnings in non debug mode */
1118 }
1119
1120 // update offset
1121 iOffset += pTriInfos[f].AssignedGroup[i]->iNrFaces;
1122 // since the groups are disjoint a triangle can never
1123 // belong to more than 3 groups. Subsequently something
1124 // is completely screwed if this assertion ever hits.
1125 assert(iOffset <= iNrMaxGroups);
1126 }
1127 }
1128 }
1129
1130 return iNrActiveGroups;
1131}
1132
1133static void AddTriToGroup(SGroup * pGroup, const int iTriIndex)
1134{
1135 pGroup->pFaceIndices[pGroup->iNrFaces] = iTriIndex;
1136 ++pGroup->iNrFaces;
1137}
1138
1139static tbool AssignRecur(const int piTriListIn[], STriInfo psTriInfos[],
1140 const int iMyTriIndex, SGroup * pGroup)
1141{
1142 STriInfo * pMyTriInfo = &psTriInfos[iMyTriIndex];
1143
1144 // track down vertex
1145 const int iVertRep = pGroup->iVertexRepresentitive;
1146 const int * pVerts = &piTriListIn[3*iMyTriIndex+0];
1147 int i=-1;
1148 if (pVerts[0]==iVertRep) i=0;
1149 else if (pVerts[1]==iVertRep) i=1;
1150 else if (pVerts[2]==iVertRep) i=2;
1151 assert(i>=0 && i<3);
1152
1153 // early out
1154 if (pMyTriInfo->AssignedGroup[i] == pGroup) return TTRUE;
1155 else if (pMyTriInfo->AssignedGroup[i]!=NULL) return TFALSE;
1156 if ((pMyTriInfo->iFlag&GROUP_WITH_ANY)!=0)
1157 {
1158 // first to group with a group-with-anything triangle
1159 // determines it's orientation.
1160 // This is the only existing order dependency in the code!!
1161 if ( pMyTriInfo->AssignedGroup[0] == NULL &&
1162 pMyTriInfo->AssignedGroup[1] == NULL &&
1163 pMyTriInfo->AssignedGroup[2] == NULL )
1164 {
1165 pMyTriInfo->iFlag &= (~ORIENT_PRESERVING);
1166 pMyTriInfo->iFlag |= (pGroup->bOrientPreservering ? ORIENT_PRESERVING : 0);
1167 }
1168 }
1169 {
1170 const tbool bOrient = (pMyTriInfo->iFlag&ORIENT_PRESERVING)!=0 ? TTRUE : TFALSE;
1171 if (bOrient != pGroup->bOrientPreservering) return TFALSE;
1172 }
1173
1174 AddTriToGroup(pGroup, iMyTriIndex);
1175 pMyTriInfo->AssignedGroup[i] = pGroup;
1176
1177 {
1178 const int neigh_indexL = pMyTriInfo->FaceNeighbors[i];
1179 const int neigh_indexR = pMyTriInfo->FaceNeighbors[i>0?(i-1):2];
1180 if (neigh_indexL>=0)
1181 AssignRecur(piTriListIn, psTriInfos, neigh_indexL, pGroup);
1182 if (neigh_indexR>=0)
1183 AssignRecur(piTriListIn, psTriInfos, neigh_indexR, pGroup);
1184 }
1185
1186
1187
1188 return TTRUE;
1189}
1190
1191/////////////////////////////////////////////////////////////////////////////////////////////////////
1192/////////////////////////////////////////////////////////////////////////////////////////////////////
1193
1194static tbool CompareSubGroups(const SSubGroup * pg1, const SSubGroup * pg2);
1195static void QuickSort(int* pSortBuffer, int iLeft, int iRight, unsigned int uSeed);
1196static STSpace EvalTspace(int face_indices[], const int iFaces, const int piTriListIn[], const STriInfo pTriInfos[], const SMikkTSpaceContext * pContext, const int iVertexRepresentitive);
1197
1198static tbool GenerateTSpaces(STSpace psTspace[], const STriInfo pTriInfos[], const SGroup pGroups[],
1199 const int iNrActiveGroups, const int piTriListIn[], const float fThresCos,
1200 const SMikkTSpaceContext * pContext)
1201{
1202 STSpace * pSubGroupTspace = NULL;
1203 SSubGroup * pUniSubGroups = NULL;
1204 int * pTmpMembers = NULL;
1205 int iMaxNrFaces=0, iUniqueTspaces=0, g=0, i=0;
1206 for (g=0; g<iNrActiveGroups; g++)
1207 if (iMaxNrFaces < pGroups[g].iNrFaces)
1208 iMaxNrFaces = pGroups[g].iNrFaces;
1209
1210 if (iMaxNrFaces == 0) return TTRUE;
1211
1212 // make initial allocations
1213 pSubGroupTspace = (STSpace *) malloc(sizeof(STSpace)*iMaxNrFaces);
1214 pUniSubGroups = (SSubGroup *) malloc(sizeof(SSubGroup)*iMaxNrFaces);
1215 pTmpMembers = (int *) malloc(sizeof(int)*iMaxNrFaces);
1216 if (pSubGroupTspace==NULL || pUniSubGroups==NULL || pTmpMembers==NULL)
1217 {
1218 if (pSubGroupTspace!=NULL) free(pSubGroupTspace);
1219 if (pUniSubGroups!=NULL) free(pUniSubGroups);
1220 if (pTmpMembers!=NULL) free(pTmpMembers);
1221 return TFALSE;
1222 }
1223
1224
1225 iUniqueTspaces = 0;
1226 for (g=0; g<iNrActiveGroups; g++)
1227 {
1228 const SGroup * pGroup = &pGroups[g];
1229 int iUniqueSubGroups = 0, s=0;
1230
1231 for (i=0; i<pGroup->iNrFaces; i++) // triangles
1232 {
1233 const int f = pGroup->pFaceIndices[i]; // triangle number
1234 int index=-1, iVertIndex=-1, iOF_1=-1, iMembers=0, j=0, l=0;
1235 SSubGroup tmp_group;
1236 tbool bFound;
1237 SVec3 n, vOs, vOt;
1238 if (pTriInfos[f].AssignedGroup[0]==pGroup) index=0;
1239 else if (pTriInfos[f].AssignedGroup[1]==pGroup) index=1;
1240 else if (pTriInfos[f].AssignedGroup[2]==pGroup) index=2;
1241 assert(index>=0 && index<3);
1242
1243 iVertIndex = piTriListIn[f*3+index];
1244 assert(iVertIndex==pGroup->iVertexRepresentitive);
1245
1246 // is normalized already
1247 n = GetNormal(pContext, iVertIndex);
1248
1249 // project
1250 vOs = vsub(pTriInfos[f].vOs, vscale(vdot(n,pTriInfos[f].vOs), n));
1251 vOt = vsub(pTriInfos[f].vOt, vscale(vdot(n,pTriInfos[f].vOt), n));
1252 if ( VNotZero(vOs) ) vOs = Normalize(vOs);
1253 if ( VNotZero(vOt) ) vOt = Normalize(vOt);
1254
1255 // original face number
1256 iOF_1 = pTriInfos[f].iOrgFaceNumber;
1257
1258 iMembers = 0;
1259 for (j=0; j<pGroup->iNrFaces; j++)
1260 {
1261 const int t = pGroup->pFaceIndices[j]; // triangle number
1262 const int iOF_2 = pTriInfos[t].iOrgFaceNumber;
1263
1264 // project
1265 SVec3 vOs2 = vsub(pTriInfos[t].vOs, vscale(vdot(n,pTriInfos[t].vOs), n));
1266 SVec3 vOt2 = vsub(pTriInfos[t].vOt, vscale(vdot(n,pTriInfos[t].vOt), n));
1267 if ( VNotZero(vOs2) ) vOs2 = Normalize(vOs2);
1268 if ( VNotZero(vOt2) ) vOt2 = Normalize(vOt2);
1269
1270 {
1271 const tbool bAny = ( (pTriInfos[f].iFlag | pTriInfos[t].iFlag) & GROUP_WITH_ANY )!=0 ? TTRUE : TFALSE;
1272 // make sure triangles which belong to the same quad are joined.
1273 const tbool bSameOrgFace = iOF_1==iOF_2 ? TTRUE : TFALSE;
1274
1275 const float fCosS = vdot(vOs,vOs2);
1276 const float fCosT = vdot(vOt,vOt2);
1277
1278 assert(f!=t || bSameOrgFace); // sanity check
1279 if (bAny || bSameOrgFace || (fCosS>fThresCos && fCosT>fThresCos))
1280 pTmpMembers[iMembers++] = t;
1281 }
1282 }
1283
1284 // sort pTmpMembers
1285 tmp_group.iNrFaces = iMembers;
1286 tmp_group.pTriMembers = pTmpMembers;
1287 if (iMembers>1)
1288 {
1289 unsigned int uSeed = INTERNAL_RND_SORT_SEED; // could replace with a random seed?
1290 QuickSort(pTmpMembers, 0, iMembers-1, uSeed);
1291 }
1292
1293 // look for an existing match
1294 bFound = TFALSE;
1295 l=0;
1296 while (l<iUniqueSubGroups && !bFound)
1297 {
1298 bFound = CompareSubGroups(&tmp_group, &pUniSubGroups[l]);
1299 if (!bFound) ++l;
1300 }
1301
1302 // assign tangent space index
1303 assert(bFound || l==iUniqueSubGroups);
1304 //piTempTangIndices[f*3+index] = iUniqueTspaces+l;
1305
1306 // if no match was found we allocate a new subgroup
1307 if (!bFound)
1308 {
1309 // insert new subgroup
1310 int * pIndices = (int *) malloc(sizeof(int)*iMembers);
1311 if (pIndices==NULL)
1312 {
1313 // clean up and return false
1314 int s=0;
1315 for (s=0; s<iUniqueSubGroups; s++)
1316 free(pUniSubGroups[s].pTriMembers);
1317 free(pUniSubGroups);
1318 free(pTmpMembers);
1319 free(pSubGroupTspace);
1320 return TFALSE;
1321 }
1322 pUniSubGroups[iUniqueSubGroups].iNrFaces = iMembers;
1323 pUniSubGroups[iUniqueSubGroups].pTriMembers = pIndices;
1324 memcpy(pIndices, tmp_group.pTriMembers, iMembers*sizeof(int));
1325 pSubGroupTspace[iUniqueSubGroups] =
1326 EvalTspace(tmp_group.pTriMembers, iMembers, piTriListIn, pTriInfos, pContext, pGroup->iVertexRepresentitive);
1327 ++iUniqueSubGroups;
1328 }
1329
1330 // output tspace
1331 {
1332 const int iOffs = pTriInfos[f].iTSpacesOffs;
1333 const int iVert = pTriInfos[f].vert_num[index];
1334 STSpace * pTS_out = &psTspace[iOffs+iVert];
1335 assert(pTS_out->iCounter<2);
1336 assert(((pTriInfos[f].iFlag&ORIENT_PRESERVING)!=0) == pGroup->bOrientPreservering);
1337 if (pTS_out->iCounter==1)
1338 {
1339 *pTS_out = AvgTSpace(pTS_out, &pSubGroupTspace[l]);
1340 pTS_out->iCounter = 2; // update counter
1341 pTS_out->bOrient = pGroup->bOrientPreservering;
1342 }
1343 else
1344 {
1345 assert(pTS_out->iCounter==0);
1346 *pTS_out = pSubGroupTspace[l];
1347 pTS_out->iCounter = 1; // update counter
1348 pTS_out->bOrient = pGroup->bOrientPreservering;
1349 }
1350 }
1351 }
1352
1353 // clean up and offset iUniqueTspaces
1354 for (s=0; s<iUniqueSubGroups; s++)
1355 free(pUniSubGroups[s].pTriMembers);
1356 iUniqueTspaces += iUniqueSubGroups;
1357 }
1358
1359 // clean up
1360 free(pUniSubGroups);
1361 free(pTmpMembers);
1362 free(pSubGroupTspace);
1363
1364 return TTRUE;
1365}
1366
1367static STSpace EvalTspace(int face_indices[], const int iFaces, const int piTriListIn[], const STriInfo pTriInfos[],
1368 const SMikkTSpaceContext * pContext, const int iVertexRepresentitive)
1369{
1370 STSpace res;
1371 float fAngleSum = 0;
1372 int face=0;
1373 res.vOs.x=0.0f; res.vOs.y=0.0f; res.vOs.z=0.0f;
1374 res.vOt.x=0.0f; res.vOt.y=0.0f; res.vOt.z=0.0f;
1375 res.fMagS = 0; res.fMagT = 0;
1376
1377 for (face=0; face<iFaces; face++)
1378 {
1379 const int f = face_indices[face];
1380
1381 // only valid triangles get to add their contribution
1382 if ( (pTriInfos[f].iFlag&GROUP_WITH_ANY)==0 )
1383 {
1384 SVec3 n, vOs, vOt, p0, p1, p2, v1, v2;
1385 float fCos, fAngle, fMagS, fMagT;
1386 int i=-1, index=-1, i0=-1, i1=-1, i2=-1;
1387 if (piTriListIn[3*f+0]==iVertexRepresentitive) i=0;
1388 else if (piTriListIn[3*f+1]==iVertexRepresentitive) i=1;
1389 else if (piTriListIn[3*f+2]==iVertexRepresentitive) i=2;
1390 assert(i>=0 && i<3);
1391
1392 // project
1393 index = piTriListIn[3*f+i];
1394 n = GetNormal(pContext, index);
1395 vOs = vsub(pTriInfos[f].vOs, vscale(vdot(n,pTriInfos[f].vOs), n));
1396 vOt = vsub(pTriInfos[f].vOt, vscale(vdot(n,pTriInfos[f].vOt), n));
1397 if ( VNotZero(vOs) ) vOs = Normalize(vOs);
1398 if ( VNotZero(vOt) ) vOt = Normalize(vOt);
1399
1400 i2 = piTriListIn[3*f + (i<2?(i+1):0)];
1401 i1 = piTriListIn[3*f + i];
1402 i0 = piTriListIn[3*f + (i>0?(i-1):2)];
1403
1404 p0 = GetPosition(pContext, i0);
1405 p1 = GetPosition(pContext, i1);
1406 p2 = GetPosition(pContext, i2);
1407 v1 = vsub(p0,p1);
1408 v2 = vsub(p2,p1);
1409
1410 // project
1411 v1 = vsub(v1, vscale(vdot(n,v1),n)); if ( VNotZero(v1) ) v1 = Normalize(v1);
1412 v2 = vsub(v2, vscale(vdot(n,v2),n)); if ( VNotZero(v2) ) v2 = Normalize(v2);
1413
1414 // weight contribution by the angle
1415 // between the two edge vectors
1416 fCos = vdot(v1,v2); fCos=fCos>1?1:(fCos<(-1) ? (-1) : fCos);
1417 fAngle = (float) acos(fCos);
1418 fMagS = pTriInfos[f].fMagS;
1419 fMagT = pTriInfos[f].fMagT;
1420
1421 res.vOs=vadd(res.vOs, vscale(fAngle,vOs));
1422 res.vOt=vadd(res.vOt,vscale(fAngle,vOt));
1423 res.fMagS+=(fAngle*fMagS);
1424 res.fMagT+=(fAngle*fMagT);
1425 fAngleSum += fAngle;
1426 }
1427 }
1428
1429 // normalize
1430 if ( VNotZero(res.vOs) ) res.vOs = Normalize(res.vOs);
1431 if ( VNotZero(res.vOt) ) res.vOt = Normalize(res.vOt);
1432 if (fAngleSum>0)
1433 {
1434 res.fMagS /= fAngleSum;
1435 res.fMagT /= fAngleSum;
1436 }
1437
1438 return res;
1439}
1440
1441static tbool CompareSubGroups(const SSubGroup * pg1, const SSubGroup * pg2)
1442{
1443 tbool bStillSame=TTRUE;
1444 int i=0;
1445 if (pg1->iNrFaces!=pg2->iNrFaces) return TFALSE;
1446 while (i<pg1->iNrFaces && bStillSame)
1447 {
1448 bStillSame = pg1->pTriMembers[i]==pg2->pTriMembers[i] ? TTRUE : TFALSE;
1449 if (bStillSame) ++i;
1450 }
1451 return bStillSame;
1452}
1453
1454static void QuickSort(int* pSortBuffer, int iLeft, int iRight, unsigned int uSeed)
1455{
1456 int iL, iR, n, index, iMid, iTmp;
1457
1458 // Random
1459 unsigned int t=uSeed&31;
1460 t=(uSeed<<t)|(uSeed>>(32-t));
1461 uSeed=uSeed+t+3;
1462 // Random end
1463
1464 iL=iLeft; iR=iRight;
1465 n = (iR-iL)+1;
1466 assert(n>=0);
1467 index = (int) (uSeed%n);
1468
1469 iMid=pSortBuffer[index + iL];
1470
1471
1472 do
1473 {
1474 while (pSortBuffer[iL] < iMid)
1475 ++iL;
1476 while (pSortBuffer[iR] > iMid)
1477 --iR;
1478
1479 if (iL <= iR)
1480 {
1481 iTmp = pSortBuffer[iL];
1482 pSortBuffer[iL] = pSortBuffer[iR];
1483 pSortBuffer[iR] = iTmp;
1484 ++iL; --iR;
1485 }
1486 }
1487 while (iL <= iR);
1488
1489 if (iLeft < iR)
1490 QuickSort(pSortBuffer, iLeft, iR, uSeed);
1491 if (iL < iRight)
1492 QuickSort(pSortBuffer, iL, iRight, uSeed);
1493}
1494
1495/////////////////////////////////////////////////////////////////////////////////////////////
1496/////////////////////////////////////////////////////////////////////////////////////////////
1497
1498static void QuickSortEdges(SEdge * pSortBuffer, int iLeft, int iRight, const int channel, unsigned int uSeed);
1499static void GetEdge(int * i0_out, int * i1_out, int * edgenum_out, const int indices[], const int i0_in, const int i1_in);
1500
1501static void BuildNeighborsFast(STriInfo pTriInfos[], SEdge * pEdges, const int piTriListIn[], const int iNrTrianglesIn)
1502{
1503 // build array of edges
1504 unsigned int uSeed = INTERNAL_RND_SORT_SEED; // could replace with a random seed?
1505 int iEntries=0, iCurStartIndex=-1, f=0, i=0;
1506 for (f=0; f<iNrTrianglesIn; f++)
1507 for (i=0; i<3; i++)
1508 {
1509 const int i0 = piTriListIn[f*3+i];
1510 const int i1 = piTriListIn[f*3+(i<2?(i+1):0)];
1511 pEdges[f*3+i].i0 = i0 < i1 ? i0 : i1; // put minimum index in i0
1512 pEdges[f*3+i].i1 = !(i0 < i1) ? i0 : i1; // put maximum index in i1
1513 pEdges[f*3+i].f = f; // record face number
1514 }
1515
1516 // sort over all edges by i0, this is the pricy one.
1517 QuickSortEdges(pEdges, 0, iNrTrianglesIn*3-1, 0, uSeed); // sort channel 0 which is i0
1518
1519 // sub sort over i1, should be fast.
1520 // could replace this with a 64 bit int sort over (i0,i1)
1521 // with i0 as msb in the quicksort call above.
1522 iEntries = iNrTrianglesIn*3;
1523 iCurStartIndex = 0;
1524 for (i=1; i<iEntries; i++)
1525 {
1526 if (pEdges[iCurStartIndex].i0 != pEdges[i].i0)
1527 {
1528 const int iL = iCurStartIndex;
1529 const int iR = i-1;
1530 //const int iElems = i-iL;
1531 iCurStartIndex = i;
1532 QuickSortEdges(pEdges, iL, iR, 1, uSeed); // sort channel 1 which is i1
1533 }
1534 }
1535
1536 // sub sort over f, which should be fast.
1537 // this step is to remain compliant with BuildNeighborsSlow() when
1538 // more than 2 triangles use the same edge (such as a butterfly topology).
1539 iCurStartIndex = 0;
1540 for (i=1; i<iEntries; i++)
1541 {
1542 if (pEdges[iCurStartIndex].i0 != pEdges[i].i0 || pEdges[iCurStartIndex].i1 != pEdges[i].i1)
1543 {
1544 const int iL = iCurStartIndex;
1545 const int iR = i-1;
1546 //const int iElems = i-iL;
1547 iCurStartIndex = i;
1548 QuickSortEdges(pEdges, iL, iR, 2, uSeed); // sort channel 2 which is f
1549 }
1550 }
1551
1552 // pair up, adjacent triangles
1553 for (i=0; i<iEntries; i++)
1554 {
1555 const int i0=pEdges[i].i0;
1556 const int i1=pEdges[i].i1;
1557 const int f = pEdges[i].f;
1558 tbool bUnassigned_A;
1559
1560 int i0_A, i1_A;
1561 int edgenum_A, edgenum_B=0; // 0,1 or 2
1562 GetEdge(&i0_A, &i1_A, &edgenum_A, &piTriListIn[f*3], i0, i1); // resolve index ordering and edge_num
1563 bUnassigned_A = pTriInfos[f].FaceNeighbors[edgenum_A] == -1 ? TTRUE : TFALSE;
1564
1565 if (bUnassigned_A)
1566 {
1567 // get true index ordering
1568 int j=i+1, t;
1569 tbool bNotFound = TTRUE;
1570 while (j<iEntries && i0==pEdges[j].i0 && i1==pEdges[j].i1 && bNotFound)
1571 {
1572 tbool bUnassigned_B;
1573 int i0_B, i1_B;
1574 t = pEdges[j].f;
1575 // flip i0_B and i1_B
1576 GetEdge(&i1_B, &i0_B, &edgenum_B, &piTriListIn[t*3], pEdges[j].i0, pEdges[j].i1); // resolve index ordering and edge_num
1577 //assert(!(i0_A==i1_B && i1_A==i0_B));
1578 bUnassigned_B = pTriInfos[t].FaceNeighbors[edgenum_B]==-1 ? TTRUE : TFALSE;
1579 if (i0_A==i0_B && i1_A==i1_B && bUnassigned_B)
1580 bNotFound = TFALSE;
1581 else
1582 ++j;
1583 }
1584
1585 if (!bNotFound)
1586 {
1587 int t = pEdges[j].f;
1588 pTriInfos[f].FaceNeighbors[edgenum_A] = t;
1589 //assert(pTriInfos[t].FaceNeighbors[edgenum_B]==-1);
1590 pTriInfos[t].FaceNeighbors[edgenum_B] = f;
1591 }
1592 }
1593 }
1594}
1595
1596static void BuildNeighborsSlow(STriInfo pTriInfos[], const int piTriListIn[], const int iNrTrianglesIn)
1597{
1598 int f=0, i=0;
1599 for (f=0; f<iNrTrianglesIn; f++)
1600 {
1601 for (i=0; i<3; i++)
1602 {
1603 // if unassigned
1604 if (pTriInfos[f].FaceNeighbors[i] == -1)
1605 {
1606 const int i0_A = piTriListIn[f*3+i];
1607 const int i1_A = piTriListIn[f*3+(i<2?(i+1):0)];
1608
1609 // search for a neighbor
1610 tbool bFound = TFALSE;
1611 int t=0, j=0;
1612 while (!bFound && t<iNrTrianglesIn)
1613 {
1614 if (t!=f)
1615 {
1616 j=0;
1617 while (!bFound && j<3)
1618 {
1619 // in rev order
1620 const int i1_B = piTriListIn[t*3+j];
1621 const int i0_B = piTriListIn[t*3+(j<2?(j+1):0)];
1622 //assert(!(i0_A==i1_B && i1_A==i0_B));
1623 if (i0_A==i0_B && i1_A==i1_B)
1624 bFound = TTRUE;
1625 else
1626 ++j;
1627 }
1628 }
1629
1630 if (!bFound) ++t;
1631 }
1632
1633 // assign neighbors
1634 if (bFound)
1635 {
1636 pTriInfos[f].FaceNeighbors[i] = t;
1637 //assert(pTriInfos[t].FaceNeighbors[j]==-1);
1638 pTriInfos[t].FaceNeighbors[j] = f;
1639 }
1640 }
1641 }
1642 }
1643}
1644
1645static void QuickSortEdges(SEdge * pSortBuffer, int iLeft, int iRight, const int channel, unsigned int uSeed)
1646{
1647 unsigned int t;
1648 int iL, iR, n, index, iMid;
1649
1650 // early out
1651 SEdge sTmp;
1652 const int iElems = iRight-iLeft+1;
1653 if (iElems<2) return;
1654 else if (iElems==2)
1655 {
1656 if (pSortBuffer[iLeft].array[channel] > pSortBuffer[iRight].array[channel])
1657 {
1658 sTmp = pSortBuffer[iLeft];
1659 pSortBuffer[iLeft] = pSortBuffer[iRight];
1660 pSortBuffer[iRight] = sTmp;
1661 }
1662 return;
1663 }
1664
1665 // Random
1666 t=uSeed&31;
1667 t=(uSeed<<t)|(uSeed>>(32-t));
1668 uSeed=uSeed+t+3;
1669 // Random end
1670
1671 iL = iLeft;
1672 iR = iRight;
1673 n = (iR-iL)+1;
1674 assert(n>=0);
1675 index = (int) (uSeed%n);
1676
1677 iMid=pSortBuffer[index + iL].array[channel];
1678
1679 do
1680 {
1681 while (pSortBuffer[iL].array[channel] < iMid)
1682 ++iL;
1683 while (pSortBuffer[iR].array[channel] > iMid)
1684 --iR;
1685
1686 if (iL <= iR)
1687 {
1688 sTmp = pSortBuffer[iL];
1689 pSortBuffer[iL] = pSortBuffer[iR];
1690 pSortBuffer[iR] = sTmp;
1691 ++iL; --iR;
1692 }
1693 }
1694 while (iL <= iR);
1695
1696 if (iLeft < iR)
1697 QuickSortEdges(pSortBuffer, iLeft, iR, channel, uSeed);
1698 if (iL < iRight)
1699 QuickSortEdges(pSortBuffer, iL, iRight, channel, uSeed);
1700}
1701
1702// resolve ordering and edge number
1703static void GetEdge(int * i0_out, int * i1_out, int * edgenum_out, const int indices[], const int i0_in, const int i1_in)
1704{
1705 *edgenum_out = -1;
1706
1707 // test if first index is on the edge
1708 if (indices[0]==i0_in || indices[0]==i1_in)
1709 {
1710 // test if second index is on the edge
1711 if (indices[1]==i0_in || indices[1]==i1_in)
1712 {
1713 edgenum_out[0]=0; // first edge
1714 i0_out[0]=indices[0];
1715 i1_out[0]=indices[1];
1716 }
1717 else
1718 {
1719 edgenum_out[0]=2; // third edge
1720 i0_out[0]=indices[2];
1721 i1_out[0]=indices[0];
1722 }
1723 }
1724 else
1725 {
1726 // only second and third index is on the edge
1727 edgenum_out[0]=1; // second edge
1728 i0_out[0]=indices[1];
1729 i1_out[0]=indices[2];
1730 }
1731}
1732
1733
1734/////////////////////////////////////////////////////////////////////////////////////////////
1735/////////////////////////////////// Degenerate triangles ////////////////////////////////////
1736
1737static void DegenPrologue(STriInfo pTriInfos[], int piTriList_out[], const int iNrTrianglesIn, const int iTotTris)
1738{
1739 int iNextGoodTriangleSearchIndex=-1;
1740 tbool bStillFindingGoodOnes;
1741
1742 // locate quads with only one good triangle
1743 int t=0;
1744 while (t<(iTotTris-1))
1745 {
1746 const int iFO_a = pTriInfos[t].iOrgFaceNumber;
1747 const int iFO_b = pTriInfos[t+1].iOrgFaceNumber;
1748 if (iFO_a==iFO_b) // this is a quad
1749 {
1750 const tbool bIsDeg_a = (pTriInfos[t].iFlag&MARK_DEGENERATE)!=0 ? TTRUE : TFALSE;
1751 const tbool bIsDeg_b = (pTriInfos[t+1].iFlag&MARK_DEGENERATE)!=0 ? TTRUE : TFALSE;
1752 if ((bIsDeg_a^bIsDeg_b)!=0)
1753 {
1754 pTriInfos[t].iFlag |= QUAD_ONE_DEGEN_TRI;
1755 pTriInfos[t+1].iFlag |= QUAD_ONE_DEGEN_TRI;
1756 }
1757 t += 2;
1758 }
1759 else
1760 ++t;
1761 }
1762
1763 // reorder list so all degen triangles are moved to the back
1764 // without reordering the good triangles
1765 iNextGoodTriangleSearchIndex = 1;
1766 t=0;
1767 bStillFindingGoodOnes = TTRUE;
1768 while (t<iNrTrianglesIn && bStillFindingGoodOnes)
1769 {
1770 const tbool bIsGood = (pTriInfos[t].iFlag&MARK_DEGENERATE)==0 ? TTRUE : TFALSE;
1771 if (bIsGood)
1772 {
1773 if (iNextGoodTriangleSearchIndex < (t+2))
1774 iNextGoodTriangleSearchIndex = t+2;
1775 }
1776 else
1777 {
1778 int t0, t1;
1779 // search for the first good triangle.
1780 tbool bJustADegenerate = TTRUE;
1781 while (bJustADegenerate && iNextGoodTriangleSearchIndex<iTotTris)
1782 {
1783 const tbool bIsGood = (pTriInfos[iNextGoodTriangleSearchIndex].iFlag&MARK_DEGENERATE)==0 ? TTRUE : TFALSE;
1784 if (bIsGood) bJustADegenerate=TFALSE;
1785 else ++iNextGoodTriangleSearchIndex;
1786 }
1787
1788 t0 = t;
1789 t1 = iNextGoodTriangleSearchIndex;
1790 ++iNextGoodTriangleSearchIndex;
1791 assert(iNextGoodTriangleSearchIndex > (t+1));
1792
1793 // swap triangle t0 and t1
1794 if (!bJustADegenerate)
1795 {
1796 int i=0;
1797 for (i=0; i<3; i++)
1798 {
1799 const int index = piTriList_out[t0*3+i];
1800 piTriList_out[t0*3+i] = piTriList_out[t1*3+i];
1801 piTriList_out[t1*3+i] = index;
1802 }
1803 {
1804 const STriInfo tri_info = pTriInfos[t0];
1805 pTriInfos[t0] = pTriInfos[t1];
1806 pTriInfos[t1] = tri_info;
1807 }
1808 }
1809 else
1810 bStillFindingGoodOnes = TFALSE; // this is not supposed to happen
1811 }
1812
1813 if (bStillFindingGoodOnes) ++t;
1814 }
1815
1816 assert(bStillFindingGoodOnes); // code will still work.
1817 assert(iNrTrianglesIn == t);
1818}
1819
1820static void DegenEpilogue(STSpace psTspace[], STriInfo pTriInfos[], int piTriListIn[], const SMikkTSpaceContext * pContext, const int iNrTrianglesIn, const int iTotTris)
1821{
1822 int t=0, i=0;
1823 // deal with degenerate triangles
1824 // punishment for degenerate triangles is O(N^2)
1825 for (t=iNrTrianglesIn; t<iTotTris; t++)
1826 {
1827 // degenerate triangles on a quad with one good triangle are skipped
1828 // here but processed in the next loop
1829 const tbool bSkip = (pTriInfos[t].iFlag&QUAD_ONE_DEGEN_TRI)!=0 ? TTRUE : TFALSE;
1830
1831 if (!bSkip)
1832 {
1833 for (i=0; i<3; i++)
1834 {
1835 const int index1 = piTriListIn[t*3+i];
1836 // search through the good triangles
1837 tbool bNotFound = TTRUE;
1838 int j=0;
1839 while (bNotFound && j<(3*iNrTrianglesIn))
1840 {
1841 const int index2 = piTriListIn[j];
1842 if (index1==index2) bNotFound=TFALSE;
1843 else ++j;
1844 }
1845
1846 if (!bNotFound)
1847 {
1848 const int iTri = j/3;
1849 const int iVert = j%3;
1850 const int iSrcVert=pTriInfos[iTri].vert_num[iVert];
1851 const int iSrcOffs=pTriInfos[iTri].iTSpacesOffs;
1852 const int iDstVert=pTriInfos[t].vert_num[i];
1853 const int iDstOffs=pTriInfos[t].iTSpacesOffs;
1854
1855 // copy tspace
1856 psTspace[iDstOffs+iDstVert] = psTspace[iSrcOffs+iSrcVert];
1857 }
1858 }
1859 }
1860 }
1861
1862 // deal with degenerate quads with one good triangle
1863 for (t=0; t<iNrTrianglesIn; t++)
1864 {
1865 // this triangle belongs to a quad where the
1866 // other triangle is degenerate
1867 if ( (pTriInfos[t].iFlag&QUAD_ONE_DEGEN_TRI)!=0 )
1868 {
1869 SVec3 vDstP;
1870 int iOrgF=-1, i=0;
1871 tbool bNotFound;
1872 unsigned char * pV = pTriInfos[t].vert_num;
1873 int iFlag = (1<<pV[0]) | (1<<pV[1]) | (1<<pV[2]);
1874 int iMissingIndex = 0;
1875 if ((iFlag&2)==0) iMissingIndex=1;
1876 else if ((iFlag&4)==0) iMissingIndex=2;
1877 else if ((iFlag&8)==0) iMissingIndex=3;
1878
1879 iOrgF = pTriInfos[t].iOrgFaceNumber;
1880 vDstP = GetPosition(pContext, MakeIndex(iOrgF, iMissingIndex));
1881 bNotFound = TTRUE;
1882 i=0;
1883 while (bNotFound && i<3)
1884 {
1885 const int iVert = pV[i];
1886 const SVec3 vSrcP = GetPosition(pContext, MakeIndex(iOrgF, iVert));
1887 if (veq(vSrcP, vDstP)==TTRUE)
1888 {
1889 const int iOffs = pTriInfos[t].iTSpacesOffs;
1890 psTspace[iOffs+iMissingIndex] = psTspace[iOffs+iVert];
1891 bNotFound=TFALSE;
1892 }
1893 else
1894 ++i;
1895 }
1896 assert(!bNotFound);
1897 }
1898 }
1899}
diff --git a/contrib/cgltf-tangents/MikkTSpace/mikktspace.h b/contrib/cgltf-tangents/MikkTSpace/mikktspace.h
new file mode 100644
index 0000000..52c44a7
--- /dev/null
+++ b/contrib/cgltf-tangents/MikkTSpace/mikktspace.h
@@ -0,0 +1,145 @@
1/** \file mikktspace/mikktspace.h
2 * \ingroup mikktspace
3 */
4/**
5 * Copyright (C) 2011 by Morten S. Mikkelsen
6 *
7 * This software is provided 'as-is', without any express or implied
8 * warranty. In no event will the authors be held liable for any damages
9 * arising from the use of this software.
10 *
11 * Permission is granted to anyone to use this software for any purpose,
12 * including commercial applications, and to alter it and redistribute it
13 * freely, subject to the following restrictions:
14 *
15 * 1. The origin of this software must not be misrepresented; you must not
16 * claim that you wrote the original software. If you use this software
17 * in a product, an acknowledgment in the product documentation would be
18 * appreciated but is not required.
19 * 2. Altered source versions must be plainly marked as such, and must not be
20 * misrepresented as being the original software.
21 * 3. This notice may not be removed or altered from any source distribution.
22 */
23
24#ifndef __MIKKTSPACE_H__
25#define __MIKKTSPACE_H__
26
27
28#ifdef __cplusplus
29extern "C" {
30#endif
31
32/* Author: Morten S. Mikkelsen
33 * Version: 1.0
34 *
35 * The files mikktspace.h and mikktspace.c are designed to be
36 * stand-alone files and it is important that they are kept this way.
37 * Not having dependencies on structures/classes/libraries specific
38 * to the program, in which they are used, allows them to be copied
39 * and used as is into any tool, program or plugin.
40 * The code is designed to consistently generate the same
41 * tangent spaces, for a given mesh, in any tool in which it is used.
42 * This is done by performing an internal welding step and subsequently an order-independent evaluation
43 * of tangent space for meshes consisting of triangles and quads.
44 * This means faces can be received in any order and the same is true for
45 * the order of vertices of each face. The generated result will not be affected
46 * by such reordering. Additionally, whether degenerate (vertices or texture coordinates)
47 * primitives are present or not will not affect the generated results either.
48 * Once tangent space calculation is done the vertices of degenerate primitives will simply
49 * inherit tangent space from neighboring non degenerate primitives.
50 * The analysis behind this implementation can be found in my master's thesis
51 * which is available for download --> http://image.diku.dk/projects/media/morten.mikkelsen.08.pdf
52 * Note that though the tangent spaces at the vertices are generated in an order-independent way,
53 * by this implementation, the interpolated tangent space is still affected by which diagonal is
54 * chosen to split each quad. A sensible solution is to have your tools pipeline always
55 * split quads by the shortest diagonal. This choice is order-independent and works with mirroring.
56 * If these have the same length then compare the diagonals defined by the texture coordinates.
57 * XNormal which is a tool for baking normal maps allows you to write your own tangent space plugin
58 * and also quad triangulator plugin.
59 */
60
61
62typedef int tbool;
63typedef struct SMikkTSpaceContext SMikkTSpaceContext;
64
65typedef struct {
66 // Returns the number of faces (triangles/quads) on the mesh to be processed.
67 int (*m_getNumFaces)(const SMikkTSpaceContext * pContext);
68
69 // Returns the number of vertices on face number iFace
70 // iFace is a number in the range {0, 1, ..., getNumFaces()-1}
71 int (*m_getNumVerticesOfFace)(const SMikkTSpaceContext * pContext, const int iFace);
72
73 // returns the position/normal/texcoord of the referenced face of vertex number iVert.
74 // iVert is in the range {0,1,2} for triangles and {0,1,2,3} for quads.
75 void (*m_getPosition)(const SMikkTSpaceContext * pContext, float fvPosOut[], const int iFace, const int iVert);
76 void (*m_getNormal)(const SMikkTSpaceContext * pContext, float fvNormOut[], const int iFace, const int iVert);
77 void (*m_getTexCoord)(const SMikkTSpaceContext * pContext, float fvTexcOut[], const int iFace, const int iVert);
78
79 // either (or both) of the two setTSpace callbacks can be set.
80 // The call-back m_setTSpaceBasic() is sufficient for basic normal mapping.
81
82 // This function is used to return the tangent and fSign to the application.
83 // fvTangent is a unit length vector.
84 // For normal maps it is sufficient to use the following simplified version of the bitangent which is generated at pixel/vertex level.
85 // bitangent = fSign * cross(vN, tangent);
86 // Note that the results are returned unindexed. It is possible to generate a new index list
87 // But averaging/overwriting tangent spaces by using an already existing index list WILL produce INCRORRECT results.
88 // DO NOT! use an already existing index list.
89 void (*m_setTSpaceBasic)(const SMikkTSpaceContext * pContext, const float fvTangent[], const float fSign, const int iFace, const int iVert);
90
91 // This function is used to return tangent space results to the application.
92 // fvTangent and fvBiTangent are unit length vectors and fMagS and fMagT are their
93 // true magnitudes which can be used for relief mapping effects.
94 // fvBiTangent is the "real" bitangent and thus may not be perpendicular to fvTangent.
95 // However, both are perpendicular to the vertex normal.
96 // For normal maps it is sufficient to use the following simplified version of the bitangent which is generated at pixel/vertex level.
97 // fSign = bIsOrientationPreserving ? 1.0f : (-1.0f);
98 // bitangent = fSign * cross(vN, tangent);
99 // Note that the results are returned unindexed. It is possible to generate a new index list
100 // But averaging/overwriting tangent spaces by using an already existing index list WILL produce INCRORRECT results.
101 // DO NOT! use an already existing index list.
102 void (*m_setTSpace)(const SMikkTSpaceContext * pContext, const float fvTangent[], const float fvBiTangent[], const float fMagS, const float fMagT,
103 const tbool bIsOrientationPreserving, const int iFace, const int iVert);
104} SMikkTSpaceInterface;
105
106struct SMikkTSpaceContext
107{
108 SMikkTSpaceInterface * m_pInterface; // initialized with callback functions
109 void * m_pUserData; // pointer to client side mesh data etc. (passed as the first parameter with every interface call)
110};
111
112// these are both thread safe!
113tbool genTangSpaceDefault(const SMikkTSpaceContext * pContext); // Default (recommended) fAngularThreshold is 180 degrees (which means threshold disabled)
114tbool genTangSpace(const SMikkTSpaceContext * pContext, const float fAngularThreshold);
115
116
117// To avoid visual errors (distortions/unwanted hard edges in lighting), when using sampled normal maps, the
118// normal map sampler must use the exact inverse of the pixel shader transformation.
119// The most efficient transformation we can possibly do in the pixel shader is
120// achieved by using, directly, the "unnormalized" interpolated tangent, bitangent and vertex normal: vT, vB and vN.
121// pixel shader (fast transform out)
122// vNout = normalize( vNt.x * vT + vNt.y * vB + vNt.z * vN );
123// where vNt is the tangent space normal. The normal map sampler must likewise use the
124// interpolated and "unnormalized" tangent, bitangent and vertex normal to be compliant with the pixel shader.
125// sampler does (exact inverse of pixel shader):
126// float3 row0 = cross(vB, vN);
127// float3 row1 = cross(vN, vT);
128// float3 row2 = cross(vT, vB);
129// float fSign = dot(vT, row0)<0 ? -1 : 1;
130// vNt = normalize( fSign * float3(dot(vNout,row0), dot(vNout,row1), dot(vNout,row2)) );
131// where vNout is the sampled normal in some chosen 3D space.
132//
133// Should you choose to reconstruct the bitangent in the pixel shader instead
134// of the vertex shader, as explained earlier, then be sure to do this in the normal map sampler also.
135// Finally, beware of quad triangulations. If the normal map sampler doesn't use the same triangulation of
136// quads as your renderer then problems will occur since the interpolated tangent spaces will differ
137// eventhough the vertex level tangent spaces match. This can be solved either by triangulating before
138// sampling/exporting or by using the order-independent choice of diagonal for splitting quads suggested earlier.
139// However, this must be used both by the sampler and your tools/rendering pipeline.
140
141#ifdef __cplusplus
142}
143#endif
144
145#endif
diff --git a/contrib/cgltf-tangents/README.md b/contrib/cgltf-tangents/README.md
new file mode 100644
index 0000000..2a68b27
--- /dev/null
+++ b/contrib/cgltf-tangents/README.md
@@ -0,0 +1,42 @@
1# cgltf-tangents
2
3A library to compute missing tangent vectors in glTF models using MikkTSpace.
4
5## Example
6
7```
8// Load the glTF scene and buffers as usual.
9cgltf_result result = cgltf_parse_file(&options, filepath, &data);
10cgltf_load_buffers(&options, data, filepath);
11
12// Compute missing tangents.
13cgltfTangentBuffer* tangent_buffers = 0;
14cgltf_size num_tangent_buffers = 0;
15cgltf_compute_tangents(&options, data, &tangent_buffers, &num_tangent_buffers);
16```
17
18## About
19
20This is a single-header/source library that combines
21[MikkTSpace](https://github.com/mmikk/MikkTSpace) and
22[cgltf](https://github.com/jkuhlmann/cgltf) to compute missing tangent vectors
23for models.
24
25Mesh primitives in glTF may have a normal map but not necessarily tangent
26vectors. An example is the
27[DamagedHelmet](https://github.com/KhronosGroup/glTF-Sample-Models/tree/master/2.0/DamagedHelmet/glTF)
28sample. From the
29[spec](https://registry.khronos.org/glTF/specs/2.0/glTF-2.0.html#meshes):
30
31*"When tangents are not specified, client implementations SHOULD calculate
32tangents using default MikkTSpace algorithms with the specified vertex
33positions, normals, and texture coordinates associated with the normal texture."*
34
35cgltf-tangents takes an input glTF scene and scans it for mesh primitives that
36have a normal map but no tangents. cgltf-tangents then invokes MikkTSpace to
37compute tangents for those mesh primitives and outputs an array of tangent
38buffers. The client can then upload these buffers to GPU memory for rendering.
39
40See `test/` for a complete example.
41
42MikkTSpace is packaged here for convenience. cgltf must be obtained separately.
diff --git a/contrib/cgltf-tangents/cgltf_tangents.c b/contrib/cgltf-tangents/cgltf_tangents.c
new file mode 100644
index 0000000..80b1e56
--- /dev/null
+++ b/contrib/cgltf-tangents/cgltf_tangents.c
@@ -0,0 +1,618 @@
1/*
2Copyright 2022 Marc Sunet
3
4Redistribution and use in source and binary forms, with or without modification,
5are permitted provided that the following conditions are met:
6
71. Redistributions of source code must retain the above copyright notice, this
8list of conditions and the following disclaimer.
9
102. Redistributions in binary form must reproduce the above copyright notice,
11this list of conditions and the following disclaimer in the documentation and/or
12other materials provided with the distribution.
13
14THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
15ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
16WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
17DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR
18ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
19(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
20LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
21ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
23SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24*/
25#include "cgltf_tangents.h"
26#include "cgltf.h"
27
28#include "MikkTSpace/mikktspace.h"
29
30#include <assert.h>
31#include <stdbool.h>
32#include <stdint.h>
33#include <stdlib.h>
34#include <string.h>
35
36#ifdef CGLTF_TANGENTS_DEBUG
37#include <stdio.h>
38#define DLOG printf
39#else
40#define DLOG(...)
41#endif
42
43#include <stdio.h> // TODO: Remove me.
44
45#define CGLTF_OPTIONS_MALLOC(size) \
46 options->memory.alloc(options->memory.user_data, size)
47
48#define CGLTF_OPTIONS_FREE(ptr) \
49 options->memory.free(options->memory.user_data, ptr)
50
51static void* cgltf_default_alloc(void* user, cgltf_size size) {
52 (void)user;
53 return malloc(size);
54}
55
56static void cgltf_default_free(void* user, void* ptr) {
57 (void)user;
58 free(ptr);
59}
60
61static const cgltf_size NUM_TANGENT_COMPONENTS = 4; // X,Y,Z,fSign
62
63static float normalize_i8(int8_t x) { return (float)x / 128.0; }
64static float normalize_u8(uint8_t x) { return (float)x / 255.0; }
65static float normalize_i16(int16_t x) { return (float)x / 32768.0; }
66static float normalize_u16(uint16_t x) { return (float)x / 65535.0; }
67static float normalize_u32(uint32_t x) { return (float)x / 4294967295.0; }
68
69static cgltf_size num_vertex_attrib_components(cgltf_type type) {
70 switch (type) {
71 case cgltf_type_scalar:
72 return 1;
73 case cgltf_type_vec2:
74 return 2;
75 case cgltf_type_vec3:
76 return 3;
77 case cgltf_type_vec4:
78 return 4;
79 default:
80 assert(false);
81 return 0;
82 }
83}
84
85static cgltf_size cgltf_component_type_size_bytes(cgltf_component_type type) {
86 switch (type) {
87 case cgltf_component_type_r_8:
88 return 1;
89 case cgltf_component_type_r_8u:
90 return 1;
91 case cgltf_component_type_r_16:
92 return 2;
93 case cgltf_component_type_r_16u:
94 return 2;
95 case cgltf_component_type_r_32u:
96 return 4;
97 case cgltf_component_type_r_32f:
98 return 4;
99 default:
100 assert(false);
101 return 0;
102 }
103}
104
105static cgltf_size default_stride(cgltf_type type,
106 cgltf_component_type component_type) {
107 return num_vertex_attrib_components(type) *
108 cgltf_component_type_size_bytes(component_type);
109}
110
111// -----------------------------------------------------------------------------
112// MikkTSpace interface
113
114// An array of values for a given vertex attribute or for vertex indices.
115// For positions and normals, glTF mandates floats.
116// Texcoords and indices can be different types and vary in size: 8-bit, 16-bit,
117// or 32-bit.
118// We store void* pointers so that we can do byte pointer arithmetic.
119typedef struct Buffer {
120 const void* start; // X-coordinate of the first attribute.
121 const void* end; // One byte past the end of the buffer.
122 cgltf_size stride_bytes; // Stride in bytes between each value.
123 cgltf_component_type type; // Type of each value in the buffer.
124} Buffer;
125
126// User data for mesh processing.
127// See: https://registry.khronos.org/glTF/specs/2.0/glTF-2.0.html#meshes
128// Buffer pointers have the accessor + view offsets baked in so that we do the
129// addition only once.
130typedef struct SMikkUserData {
131 const cgltf_primitive* primitive;
132 // Index buffer may be empty (mesh primitive has no indices).
133 Buffer indices;
134 // Vertex attributes.
135 Buffer positions;
136 Buffer normals;
137 Buffer texcoords;
138 // Output tangents.
139 void* tangents;
140} SMikkUserData;
141
142static cgltf_size get_vertex_index(const SMikkUserData* data, cgltf_size iFace,
143 cgltf_size iVert) {
144 const cgltf_primitive* primitive = data->primitive;
145
146 // First compute a vertex index as if the mesh primitive had no indices.
147 cgltf_size vertex_idx = 0;
148 switch (primitive->type) {
149 case cgltf_primitive_type_triangles:
150 vertex_idx = iFace * 3 + iVert;
151 break;
152 case cgltf_primitive_type_triangle_strip:
153 // For triangle strips:
154 // face 0 -> verts 0, 1, 2
155 // face 1 -> verts 1, 3, 2 (1, 2, 3 flipped)
156 // face 2 -> verts 2, 3, 4
157 // face 3 -> verts 3, 5, 4 (3, 4, 5 flipped)
158 // ...
159 // face N=2k -> verts N, N+1, N+2
160 // face N=2k+1 -> verts N, N+2, N+1
161 if (iFace & 1) {
162 // Flip the winding of odd faces so that the is consistent with the even
163 // ones.
164 // iVert = 0 -> vert 0
165 // iVert = 1 -> vert 2
166 // iVert = 2 -> vert 1
167 vertex_idx = iFace + (2 - iVert);
168 } else {
169 vertex_idx = iFace + iVert;
170 }
171 break;
172 case cgltf_primitive_type_triangle_fan:
173 // For triangle fans:
174 // face 0 -> verts 0, 1, 2
175 // face 1 -> verts 0, 2, 3
176 // face 2 -> verts 0, 3, 4
177 // face 3 -> verts 0, 4, 5
178 // ...
179 // face N -> verts 0, N=1, N=2
180 if (iVert == 0) {
181 vertex_idx = 0;
182 } else {
183 vertex_idx = iFace + iVert;
184 }
185 break;
186 default:
187 assert(false);
188 break;
189 }
190
191 // If the mesh primitive has vertex indices, then vertex_idx is actually the
192 // index of the index. Index the index buffer with vertex_idx to find the
193 // real vertex index.
194 if (primitive->indices != NULL) {
195 const void* p_idx =
196 data->indices.start + vertex_idx * data->indices.stride_bytes;
197 switch (data->indices.type) {
198 case cgltf_component_type_r_8:
199 vertex_idx = *((int8_t*)p_idx);
200 break;
201 case cgltf_component_type_r_8u:
202 vertex_idx = *((uint8_t*)p_idx);
203 break;
204 case cgltf_component_type_r_16:
205 vertex_idx = *((int16_t*)p_idx);
206 break;
207 case cgltf_component_type_r_16u:
208 vertex_idx = *((uint16_t*)p_idx);
209 break;
210 case cgltf_component_type_r_32u:
211 vertex_idx = *((uint32_t*)p_idx);
212 break;
213 default:
214 assert(false);
215 break;
216 }
217 }
218
219 return vertex_idx;
220}
221
222static const void* get_vertex(const Buffer* buffer, cgltf_size index) {
223 // Stride is the offset in bytes between vertex attributes.
224 const void* vertex = buffer->start + buffer->stride_bytes * index;
225 assert(vertex < buffer->end);
226 return vertex;
227}
228
229static const void* get_position(const SMikkUserData* data, cgltf_size index) {
230 return get_vertex(&data->positions, index);
231}
232
233static const void* get_normal(const SMikkUserData* data, cgltf_size index) {
234 return get_vertex(&data->normals, index);
235}
236
237static const void* get_texcoord(const SMikkUserData* data, cgltf_size index) {
238 return get_vertex(&data->texcoords, index);
239}
240
241static float* get_tangent(void* buffer, cgltf_size index) {
242 // Tangents are tightly packed.
243 return (float*)(buffer) + NUM_TANGENT_COMPONENTS * index;
244}
245
246static int SMikk_get_num_faces(const SMikkTSpaceContext* pContext) {
247 SMikkUserData* data = (SMikkUserData*)pContext->m_pUserData;
248 const cgltf_primitive* primitive = data->primitive;
249
250 // Find the number of effective vertices (vertices or indices) in the mesh
251 // primitive.
252 //
253 // https://registry.khronos.org/glTF/specs/2.0/glTF-2.0.html#meshes
254 //
255 // "All attribute accessors for a given primitive MUST have the same count.
256 // When indices property is not defined, attribute accessors' count indicates
257 // the number of vertices to render; when indices property is defined, it
258 // indicates the upper (exclusive) bound on the index values in the indices
259 // accessor, i.e., all index values MUST be less than attribute accessors'
260 // count."
261 const cgltf_size num_verts = (primitive->indices != NULL)
262 ? primitive->indices->count
263 : primitive->attributes_count;
264
265 // Determine the number of faces given the number of vertices.
266 //
267 // We use the fact that glTF only supports triangles for faces.
268 // https://registry.khronos.org/glTF/specs/2.0/glTF-2.0.html#meshes
269 switch (primitive->type) {
270 case cgltf_primitive_type_triangles:
271 return (int)num_verts / 3;
272 case cgltf_primitive_type_triangle_strip:
273 case cgltf_primitive_type_triangle_fan:
274 return (int)num_verts - 2;
275 default:
276 return 0;
277 }
278}
279
280int SMikk_get_num_vertices_of_face(const SMikkTSpaceContext* pContext,
281 const int iFace) {
282 // Triangles are the only faces supported by glTF.
283 // https://registry.khronos.org/glTF/specs/2.0/glTF-2.0.html#meshes
284 return 3;
285}
286
287void SMikk_get_position(const SMikkTSpaceContext* pContext, float fvPosOut[],
288 const int iFace, const int iVert) {
289 const SMikkUserData* data = (SMikkUserData*)pContext->m_pUserData;
290 const cgltf_primitive* primitive = data->primitive;
291
292 const cgltf_size idx = get_vertex_index(data, iFace, iVert);
293 const float* coord = get_position(data, idx);
294 fvPosOut[0] = *coord++;
295 fvPosOut[1] = *coord++;
296 fvPosOut[2] = *coord;
297 DLOG("Position (face: %d, vert: %d): %f, %f, %f; idx: %lu\n", iFace, iVert,
298 fvPosOut[0], fvPosOut[1], fvPosOut[2], idx);
299}
300
301void SMikk_get_normal(const SMikkTSpaceContext* pContext, float fvNormOut[],
302 const int iFace, const int iVert) {
303 const SMikkUserData* data = (SMikkUserData*)pContext->m_pUserData;
304 const cgltf_primitive* primitive = data->primitive;
305
306 const cgltf_size idx = get_vertex_index(data, iFace, iVert);
307 const float* coord = get_normal(data, idx);
308 fvNormOut[0] = *coord++;
309 fvNormOut[1] = *coord++;
310 fvNormOut[2] = *coord;
311 DLOG("Normal (face: %d, vert: %d): %f, %f, %f\n", iFace, iVert, fvNormOut[0],
312 fvNormOut[1], fvNormOut[2]);
313}
314
315void SMikk_get_texcoord(const SMikkTSpaceContext* pContext, float fvTexcOut[],
316 const int iFace, const int iVert) {
317 const SMikkUserData* data = (SMikkUserData*)pContext->m_pUserData;
318 const cgltf_primitive* primitive = data->primitive;
319
320 const cgltf_size idx = get_vertex_index(data, iFace, iVert);
321 const void* coord = get_texcoord(data, idx);
322 switch (data->texcoords.type) {
323 case cgltf_component_type_r_8: {
324 const int8_t* c = coord;
325 fvTexcOut[0] = normalize_i8(*c++);
326 fvTexcOut[1] = normalize_i8(*c);
327 break;
328 }
329 case cgltf_component_type_r_8u: {
330 const uint8_t* c = coord;
331 fvTexcOut[0] = normalize_u8(*c++);
332 fvTexcOut[1] = normalize_u8(*c);
333 break;
334 }
335 case cgltf_component_type_r_16: {
336 const int16_t* c = coord;
337 fvTexcOut[0] = normalize_i16(*c++);
338 fvTexcOut[1] = normalize_i16(*c);
339 break;
340 }
341 case cgltf_component_type_r_16u: {
342 const uint16_t* c = coord;
343 fvTexcOut[0] = normalize_u16(*c++);
344 fvTexcOut[1] = normalize_u16(*c);
345 break;
346 }
347 case cgltf_component_type_r_32u: {
348 const uint32_t* c = coord;
349 fvTexcOut[0] = normalize_u32(*c++);
350 fvTexcOut[1] = normalize_u32(*c);
351 break;
352 }
353 case cgltf_component_type_r_32f: {
354 const float* c = coord;
355 fvTexcOut[0] = *c++;
356 fvTexcOut[1] = *c;
357 break;
358 }
359 default:
360 assert(false);
361 break;
362 }
363 DLOG("Texcoord (face: %d, vert: %d): %f, %f\n", iFace, iVert, fvTexcOut[0],
364 fvTexcOut[1]);
365}
366
367void SMikk_set_TSpace_basic(const SMikkTSpaceContext* pContext,
368 const float fvTangent[], const float fSign,
369 const int iFace, const int iVert) {
370 SMikkUserData* data = (SMikkUserData*)pContext->m_pUserData;
371 const cgltf_primitive* primitive = data->primitive;
372
373 const cgltf_size idx = get_vertex_index(data, iFace, iVert);
374 float* coord = get_tangent(data->tangents, idx);
375 *coord++ = fvTangent[0];
376 *coord++ = fvTangent[1];
377 *coord++ = fvTangent[2];
378 *coord = fSign;
379 DLOG("Tangent (face: %d, vert: %d): %f, %f, %f; sign: %f\n", iFace, iVert,
380 fvTangent[0], fvTangent[1], fvTangent[2], fSign);
381}
382
383// -----------------------------------------------------------------------------
384
385static bool has_normal_map(const cgltf_primitive* primitive) {
386 return (primitive->material != NULL) &&
387 (primitive->material->normal_texture.texture != NULL);
388}
389
390static const cgltf_attribute* find_attribute(const cgltf_primitive* primitive,
391 cgltf_attribute_type type) {
392 for (cgltf_size i = 0; i < primitive->attributes_count; ++i) {
393 const cgltf_attribute* attrib = &primitive->attributes[i];
394 if (attrib->type == type) {
395 return attrib;
396 }
397 }
398 return NULL;
399}
400
401static bool has_attribute(const cgltf_primitive* primitive,
402 cgltf_attribute_type type) {
403 return find_attribute(primitive, type) != NULL;
404}
405
406static bool has_positions3d(const cgltf_primitive* primitive) {
407 const cgltf_attribute* attrib =
408 find_attribute(primitive, cgltf_attribute_type_position);
409 if (attrib) {
410 return attrib->data->type == cgltf_type_vec3;
411 }
412 return false;
413}
414
415static bool has_normals(const cgltf_primitive* primitive) {
416 return has_attribute(primitive, cgltf_attribute_type_normal);
417}
418
419static bool has_texcoords(const cgltf_primitive* primitive) {
420 return has_attribute(primitive, cgltf_attribute_type_texcoord);
421}
422
423static bool has_tangents(const cgltf_primitive* primitive) {
424 return has_attribute(primitive, cgltf_attribute_type_tangent);
425}
426
427static bool has_indices(const cgltf_primitive* primitive) {
428 return primitive->indices != 0;
429}
430
431static cgltfTangentBuffer compute_tangents(const cgltf_options* options,
432 const cgltf_data* data,
433 cgltf_primitive* primitive) {
434 cgltfTangentBuffer buffer = {0};
435 SMikkUserData user = {0};
436 cgltf_size num_verts = 0;
437
438 user.primitive = primitive;
439
440 if (primitive->indices != NULL) {
441 const cgltf_accessor* accessor = primitive->indices;
442 const cgltf_buffer_view* view = accessor->buffer_view;
443 const cgltf_size offset_bytes = accessor->offset + view->offset;
444 const void* buffer_data = view->buffer->data + offset_bytes;
445 const void* buffer_end = view->buffer->data + view->offset + view->size;
446
447 user.indices.start = buffer_data;
448 user.indices.end = buffer_end;
449 // Indices are tightly packed, stride 0.
450 user.indices.stride_bytes =
451 default_stride(accessor->type, accessor->component_type);
452 user.indices.type = accessor->component_type;
453 }
454
455 for (cgltf_size i = 0; i < primitive->attributes_count; ++i) {
456 const cgltf_attribute* attrib = &primitive->attributes[i];
457
458 if ((attrib->type == cgltf_attribute_type_position) ||
459 (attrib->type == cgltf_attribute_type_normal) ||
460 (attrib->type == cgltf_attribute_type_texcoord)) {
461 const cgltf_accessor* accessor = attrib->data;
462 const cgltf_buffer_view* view = accessor->buffer_view;
463 const cgltf_buffer* buffer = view->buffer;
464 const cgltf_size offset_bytes = accessor->offset + view->offset;
465 const cgltf_size stride_bytes =
466 view->stride > 0
467 ? view->stride
468 : default_stride(accessor->type, accessor->component_type);
469 // const cgltf_size size_bytes = view->size;
470 const void* buffer_data = view->buffer->data + offset_bytes;
471 const void* buffer_end = view->buffer->data + view->offset + view->size;
472
473 Buffer* attrib_buffer = 0;
474
475 if (attrib->type == cgltf_attribute_type_position) {
476 // glTF currently mandates vec3 for positions. Caller should ensure
477 // this.
478 assert(accessor->type == cgltf_type_vec3);
479 num_verts = attrib->data->count;
480 attrib_buffer = &user.positions;
481 } else if (attrib->type == cgltf_attribute_type_normal) {
482 attrib_buffer = &user.normals;
483 } else if (attrib->type == cgltf_attribute_type_texcoord) {
484 attrib_buffer = &user.texcoords;
485 }
486
487 attrib_buffer->start = buffer_data;
488 attrib_buffer->end = buffer_end;
489 attrib_buffer->stride_bytes = stride_bytes;
490 attrib_buffer->type = accessor->component_type;
491 }
492 }
493
494 assert(user.positions.start);
495 assert(user.positions.end);
496 assert(user.normals.start);
497 assert(user.normals.end);
498 assert(user.texcoords.start);
499 assert(user.texcoords.end);
500 assert(num_verts > 0);
501
502 const cgltf_size tangents_size_bytes =
503 num_verts * NUM_TANGENT_COMPONENTS * sizeof(float);
504
505 user.tangents = CGLTF_OPTIONS_MALLOC(tangents_size_bytes);
506 if (!user.tangents) {
507 return buffer;
508 }
509
510 SMikkTSpaceInterface interface = (SMikkTSpaceInterface){
511 .m_getNumFaces = SMikk_get_num_faces,
512 .m_getNumVerticesOfFace = SMikk_get_num_vertices_of_face,
513 .m_getPosition = SMikk_get_position,
514 .m_getNormal = SMikk_get_normal,
515 .m_getTexCoord = SMikk_get_texcoord,
516 .m_setTSpaceBasic = SMikk_set_TSpace_basic,
517 };
518 const SMikkTSpaceContext context = (SMikkTSpaceContext){
519 .m_pInterface = &interface,
520 .m_pUserData = &user,
521 };
522 if (!genTangSpaceDefault(&context)) {
523 return buffer;
524 }
525
526 buffer.data = user.tangents;
527 buffer.size_bytes = tangents_size_bytes;
528 buffer.primitive = primitive;
529
530 return buffer;
531}
532
533static void process_primitive(const cgltf_options* options,
534 const cgltf_data* data,
535 cgltf_primitive* primitive,
536 cgltfTangentBuffer* tangent_buffers,
537 cgltf_size* num_tangent_buffers) {
538 DLOG("Processing primitive\n");
539 cgltf_size cur_buffer = 0;
540 // TODO: MikkTSpace should not be used with models with vertex indices. One
541 // workaround is to unindex the mesh, compute tangents, and then re-index it.
542 if (((primitive->type == cgltf_primitive_type_triangle_fan) ||
543 (primitive->type == cgltf_primitive_type_triangle_strip) ||
544 (primitive->type == cgltf_primitive_type_triangles)) &&
545 has_normal_map(primitive) && !has_tangents(primitive) &&
546 has_positions3d(primitive) && has_normals(primitive) &&
547 has_texcoords(primitive) && !has_indices(primitive)) {
548 *num_tangent_buffers += 1;
549 if (tangent_buffers) {
550 DLOG("Model with normal map missing tangents detected\n");
551 tangent_buffers[cur_buffer] = compute_tangents(options, data, primitive);
552 if (tangent_buffers[cur_buffer].data) {
553 DLOG("Tangents computed\n");
554 }
555 cur_buffer++;
556 }
557 }
558}
559
560cgltf_result cgltf_compute_tangents(const cgltf_options* input_options,
561 const cgltf_data* data,
562 cgltfTangentBuffer** tangent_buffers,
563 cgltf_size* num_tangent_buffers) {
564 if ((input_options == NULL) || (data == NULL)) {
565 return cgltf_result_invalid_options;
566 }
567
568 DLOG("cgltf_compute_tangents\n");
569
570 cgltf_options options = *input_options;
571 if (options.memory.alloc == NULL) {
572 options.memory.alloc = &cgltf_default_alloc;
573 }
574 if (options.memory.free == NULL) {
575 options.memory.free = &cgltf_default_free;
576 }
577
578 // First pass: compute the number of tangent buffers to be created.
579 *num_tangent_buffers = 0;
580 for (cgltf_size mesh_idx = 0; mesh_idx < data->meshes_count; ++mesh_idx) {
581 const cgltf_mesh* mesh = &data->meshes[mesh_idx];
582
583 for (cgltf_size prim_idx = 0; prim_idx < mesh->primitives_count;
584 ++prim_idx) {
585 // Pass in null for the tangent buffers to just compute the number of
586 // buffers.
587 process_primitive(&options, data, &mesh->primitives[prim_idx], 0,
588 num_tangent_buffers);
589 }
590 }
591 DLOG("Number of primitives to be patched: %lu\n", *num_tangent_buffers);
592
593 // Second pass: compute the tangents.
594 if (*num_tangent_buffers > 0) {
595 *tangent_buffers =
596 options.memory.alloc(options.memory.user_data,
597 *num_tangent_buffers * sizeof(cgltfTangentBuffer));
598 if (!*tangent_buffers) {
599 return cgltf_result_out_of_memory;
600 }
601
602 cgltf_size tangent_buffers_computed = 0;
603
604 for (cgltf_size mesh_idx = 0; mesh_idx < data->meshes_count; ++mesh_idx) {
605 const cgltf_mesh* mesh = &data->meshes[mesh_idx];
606
607 for (cgltf_size prim_idx = 0; prim_idx < mesh->primitives_count;
608 ++prim_idx) {
609 process_primitive(&options, data, &mesh->primitives[prim_idx],
610 *tangent_buffers, &tangent_buffers_computed);
611 }
612 }
613
614 assert(tangent_buffers_computed == *num_tangent_buffers);
615 }
616
617 return cgltf_result_success;
618}
diff --git a/contrib/cgltf-tangents/cgltf_tangents.h b/contrib/cgltf-tangents/cgltf_tangents.h
new file mode 100644
index 0000000..79e3502
--- /dev/null
+++ b/contrib/cgltf-tangents/cgltf_tangents.h
@@ -0,0 +1,67 @@
1/*
2Copyright 2022 Marc Sunet
3
4Redistribution and use in source and binary forms, with or without modification,
5are permitted provided that the following conditions are met:
6
71. Redistributions of source code must retain the above copyright notice, this
8list of conditions and the following disclaimer.
9
102. Redistributions in binary form must reproduce the above copyright notice,
11this list of conditions and the following disclaimer in the documentation and/or
12other materials provided with the distribution.
13
14THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
15ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
16WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
17DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR
18ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
19(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
20LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
21ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
23SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24*/
25#ifndef CGLTF_TANGENTS_H_INCLUDED__
26#define CGLTF_TANGENTS_H_INCLUDED__
27
28#include <cgltf.h>
29
30/// A buffer that holds tangent vectors.
31///
32/// Tangent vectors are tightly packed in the array.
33///
34/// Tangent vectors have 4 coordinates: (X,Y,Z) for the vector, W for the sign.
35/// The usual rules of MikkTSpace apply, namely that the bitangent should be
36/// computed as:
37///
38/// bitangent = tangent.w * cross(normal, tangent.xyz);
39///
40/// Refer to the MikkTSpace documentation for more details.
41///
42/// The primitive pointer points to the mesh primitive for which the tangents in
43/// this buffer were computed. When your application loads mesh primitives, it
44/// can scan the cgltfTangetBuffer array outputed by cgltf_compute_tangents() to
45/// see whether tangents were computed for the mesh primitive.
46typedef struct cgltfTangentBuffer {
47 void* data; // X-coordinate of the first tangent vector.
48 cgltf_size size_bytes; // Total Size of data in bytes.
49 cgltf_primitive* primitive; // The primitive these tangents belong to.
50} cgltfTangentBuffer;
51
52/// Compute tangent vectors for normal-mapped mesh primitives missing them.
53///
54/// cgltf_options can be zeroed out but must be non-null.
55///
56/// cgltf_data is the scene previously loaded by cgltf.
57///
58/// out_tangent_buffers is an output array of tangent buffers, one buffer per
59/// mesh primitive for which tangents were computed.
60///
61/// out_num_tangent_buffers is the number of tangent buffers in the output
62/// array.
63cgltf_result cgltf_compute_tangents(const cgltf_options*, const cgltf_data*,
64 cgltfTangentBuffer** out_tangent_buffers,
65 cgltf_size* out_num_tangent_buffers);
66
67#endif // CGLTF_TANGENTS_H_INCLUDED__
diff --git a/contrib/cgltf-tangents/test/CMakeLists.txt b/contrib/cgltf-tangents/test/CMakeLists.txt
new file mode 100644
index 0000000..422c950
--- /dev/null
+++ b/contrib/cgltf-tangents/test/CMakeLists.txt
@@ -0,0 +1,11 @@
1cmake_minimum_required(VERSION 3.0)
2
3project (cgltf-test)
4
5add_executable(cgltf-test
6 main.c)
7
8target_link_libraries(cgltf-test
9 cgltf
10 cgltf-tangents
11 -lm)
diff --git a/contrib/cgltf-tangents/test/main.c b/contrib/cgltf-tangents/test/main.c
new file mode 100644
index 0000000..0d70008
--- /dev/null
+++ b/contrib/cgltf-tangents/test/main.c
@@ -0,0 +1,86 @@
1/*
2Copyright 2022 Marc Sunet
3
4Redistribution and use in source and binary forms, with or without modification,
5are permitted provided that the following conditions are met:
6
71. Redistributions of source code must retain the above copyright notice, this
8list of conditions and the following disclaimer.
9
102. Redistributions in binary form must reproduce the above copyright notice,
11this list of conditions and the following disclaimer in the documentation and/or
12other materials provided with the distribution.
13
14THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
15ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
16WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
17DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR
18ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
19(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
20LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
21ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
23SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24*/
25#include <cgltf_tangents.h>
26#define CGLTF_IMPLEMENTATION
27#include <cgltf.h>
28
29#include <stdio.h>
30
31void print_tangent_buffer(const cgltfTangentBuffer* buffer, int max_vectors) {
32 printf("Tangent buffer for primitive (%p) (%lu bytes):\n", buffer->primitive,
33 buffer->size_bytes);
34
35 const float* xyzw = (const float*)buffer->data;
36 const float* end = (const float*)(buffer->data + buffer->size_bytes);
37
38 for (int i = 0; i < max_vectors && xyzw < end; ++i, xyzw += 4) {
39 printf("(%3.2f, %3.2f, %3.2f, sign: %3.2f)\n", *xyzw, *(xyzw + 1),
40 *(xyzw + 2), *(xyzw + 3));
41 }
42 printf("--------------------");
43}
44
45void usage(const char* argv0) {
46 fprintf(stderr, "Usage: %s <glTF file path>\n", argv0);
47}
48
49int main(int argc, const char** argv) {
50 cgltf_options options = {0};
51 cgltf_data* data = NULL;
52
53 if (argc != 2) {
54 usage(argv[0]);
55 return 0;
56 }
57
58 const char* filepath = argv[1];
59
60 cgltf_result result = cgltf_parse_file(&options, filepath, &data);
61 if (result != cgltf_result_success) {
62 cgltf_free(data);
63 return 1;
64 }
65
66 // Must call cgltf_load_buffers() to load buffer data.
67 result = cgltf_load_buffers(&options, data, filepath);
68 if (result != cgltf_result_success) {
69 cgltf_free(data);
70 return 2;
71 }
72
73 cgltfTangentBuffer* tangent_buffers = 0;
74 cgltf_size num_tangent_buffers = 0;
75 cgltf_compute_tangents(&options, data, &tangent_buffers,
76 &num_tangent_buffers);
77
78 // cgltf scene not needed beyond this point.
79 cgltf_free(data);
80
81 for (cgltf_size i = 0; i < num_tangent_buffers; ++i) {
82 print_tangent_buffer(tangent_buffers, 10);
83 }
84
85 return 0;
86}
generated by cgit v1.2.3 (git 2.25.1) at 2025-11-29 11:35:18 +0000