Blender V5.3
mikktspace.hh
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2011 Morten S. Mikkelsen
2 * SPDX-FileCopyrightText: 2022 Blender Authors
3 *
4 * SPDX-License-Identifier: Apache-2.0 */
5
9
10#include <algorithm>
11#include <cassert>
12#include <unordered_map>
13
14#ifdef WITH_TBB
15# include <tbb/parallel_for.h>
16#endif
17
19#include "mikk_float3.hh"
20#include "mikk_util.hh"
21
22namespace mikk {
23
24static constexpr uint UNSET_ENTRY = 0xffffffffu;
25
26template<typename Mesh> class Mikktspace {
27 struct Triangle {
28 /* Stores neighboring triangle for group assignment. */
29 std::array<uint, 3> neighbor;
30 /* Stores assigned group of each vertex. */
31 std::array<uint, 3> group;
32 /* Stores vertex indices that make up the triangle. */
33 std::array<uint, 3> vertices;
34
35 /* Computed face tangent, will be accumulated into group. */
36 float3 tangent;
37
38 /* Index of the face that this triangle belongs to. */
39 uint faceIdx;
40 /* Index of the first of this triangle's vertices' TSpaces. */
41 uint tSpaceIdx;
42
43 /* Stores mapping from this triangle's vertices to the original
44 * face's vertices (relevant for quads). */
45 std::array<uint8_t, 3> faceVertex;
46
47 // flags
48 bool markDegenerate : 1;
49 bool quadOneDegenTri : 1;
50 bool groupWithAny : 1;
51 bool orientPreserving : 1;
52
53 Triangle(uint faceIdx_, uint tSpaceIdx_)
54 : tangent{0.0f},
55 faceIdx{faceIdx_},
56 tSpaceIdx{tSpaceIdx_},
57 markDegenerate{false},
58 quadOneDegenTri{false},
59 groupWithAny{true},
60 orientPreserving{false}
61 {
62 neighbor.fill(UNSET_ENTRY);
63 group.fill(UNSET_ENTRY);
64 }
65
66 void setVertices(uint8_t i0, uint8_t i1, uint8_t i2)
67 {
68 faceVertex[0] = i0;
69 faceVertex[1] = i1;
70 faceVertex[2] = i2;
71 vertices[0] = pack_index(faceIdx, i0);
72 vertices[1] = pack_index(faceIdx, i1);
73 vertices[2] = pack_index(faceIdx, i2);
74 }
75 };
76
77 struct Group {
78 float3 tangent;
79 uint vertexRepresentative;
80 bool orientPreserving;
81
82 Group(uint vertexRepresentative_, bool orientPreserving_)
83 : tangent{0.0f},
84 vertexRepresentative{vertexRepresentative_},
85 orientPreserving{orientPreserving_}
86 {
87 }
88
89 void normalizeTSpace()
90 {
91 tangent = tangent.normalize();
92 }
93
94 void accumulateTSpaceAtomic(float3 v_tangent)
95 {
96 float_add_atomic(&tangent.x, v_tangent.x);
97 float_add_atomic(&tangent.y, v_tangent.y);
98 float_add_atomic(&tangent.z, v_tangent.z);
99 }
100
101 void accumulateTSpace(float3 v_tangent)
102 {
103 tangent += v_tangent;
104 }
105 };
106
107 struct TSpace {
108 float3 tangent = float3(1.0f, 0.0f, 0.0f);
109 uint counter = 0;
110 bool orientPreserving = false;
111
112 void accumulateGroup(const Group &group)
113 {
114 assert(counter < 2);
115
116 if (counter == 0) {
117 tangent = group.tangent;
118 }
119 else if (tangent == group.tangent) {
120 // this if is important. Due to floating point precision
121 // averaging when ts0==ts1 will cause a slight difference
122 // which results in tangent space splits later on, so do nothing
123 }
124 else {
125 tangent = (tangent + group.tangent).normalize();
126 }
127
128 counter++;
129 orientPreserving = group.orientPreserving;
130 }
131 };
132
133 Mesh &mesh;
134
135 std::vector<Triangle> triangles;
136 std::vector<TSpace> tSpaces;
137 std::vector<Group> groups;
138
139 uint nrTSpaces, nrFaces, nrTriangles, totalTriangles;
140
141 int nrThreads;
142 bool isParallel;
143
144 public:
145 Mikktspace(Mesh &mesh_) : mesh(mesh_) {}
146
148 {
149 nrFaces = uint(mesh.GetNumFaces());
150
151#ifdef WITH_TBB
152 nrThreads = tbb::this_task_arena::max_concurrency();
153 isParallel = (nrThreads > 1) && (nrFaces > 10000);
154#else
155 nrThreads = 1;
156 isParallel = false;
157#endif
158
159 // make an initial triangle --> face index list
161
162 if (nrTriangles == 0) {
163 return;
164 }
165
166 // make a welded index list of identical positions and attributes (pos, norm, texc)
168
169 // mark all triangle pairs that belong to a quad with only one
170 // good triangle. These need special treatment in degenEpilogue().
171 // Additionally, move all good triangles to the start of
172 // triangles[] without changing order and
173 // put the degenerate triangles last.
175
176 if (nrTriangles == 0) {
177 // No point in building tangents if there are no non-degenerate triangles, so just zero them
178 tSpaces.resize(nrTSpaces);
179 }
180 else {
181 // evaluate triangle level attributes and neighbor list
182 initTriangle();
183
184 // match up edge pairs
186
187 // based on the 4 rules, identify groups based on connectivity
189
190 // make tspaces, each group is split up into subgroups.
191 // Finally a tangent space is made for every resulting subgroup
193
194 // degenerate quads with one good triangle will be fixed by copying a space from
195 // the good triangle to the coinciding vertex.
196 // all other degenerate triangles will just copy a space from any good triangle
197 // with the same welded index in vertices[].
199 }
200
201 uint index = 0;
202 for (uint f = 0; f < nrFaces; f++) {
203 const uint verts = mesh.GetNumVerticesOfFace(f);
204 if (verts != 3 && verts != 4) {
205 continue;
206 }
207
208 // set data
209 for (uint i = 0; i < verts; i++) {
210 const TSpace &tSpace = tSpaces[index++];
211 mesh.SetTangentSpace(f, i, tSpace.tangent, tSpace.orientPreserving);
212 }
213 }
214 }
215
216 protected:
217 template<typename F> void runParallel(uint start, uint end, F func)
218 {
219#ifdef WITH_TBB
220 if (isParallel) {
221 tbb::parallel_for(start, end, func);
222 }
223 else
224#endif
225 {
226 for (uint i = start; i < end; i++) {
227 func(i);
228 }
229 }
230 }
231
234
235 float3 getPosition(uint vertexID)
236 {
237 uint f, v;
238 unpack_index(f, v, vertexID);
239 return mesh.GetPosition(f, v);
240 }
241
242 float3 getNormal(uint vertexID)
243 {
244 uint f, v;
245 unpack_index(f, v, vertexID);
246 return mesh.GetNormal(f, v);
247 }
248
249 float3 getTexCoord(uint vertexID)
250 {
251 uint f, v;
252 unpack_index(f, v, vertexID);
253 return mesh.GetTexCoord(f, v);
254 }
255
256 bool has_uv() const
257 {
258 return mesh.has_uv();
259 }
260
263
265 {
266 nrTriangles = 0;
267 for (uint f = 0; f < nrFaces; f++) {
268 const uint verts = mesh.GetNumVerticesOfFace(f);
269 if (verts == 3) {
270 nrTriangles += 1;
271 }
272 else if (verts == 4) {
273 nrTriangles += 2;
274 }
275 }
276
277 triangles.reserve(nrTriangles);
278
279 nrTSpaces = 0;
280 for (uint f = 0; f < nrFaces; f++) {
281 const uint verts = mesh.GetNumVerticesOfFace(f);
282 if (verts != 3 && verts != 4) {
283 continue;
284 }
285
286 uint tA = uint(triangles.size());
287 triangles.emplace_back(f, nrTSpaces);
288 Triangle &triA = triangles[tA];
289
290 if (verts == 3) {
291 triA.setVertices(0, 1, 2);
292 }
293 else {
294 uint tB = uint(triangles.size());
295 triangles.emplace_back(f, nrTSpaces);
296 Triangle &triB = triangles[tB];
297
298 // need an order independent way to evaluate
299 // tspace on quads. This is done by splitting
300 // along the shortest diagonal.
301 float distSQ_02 = (mesh.GetTexCoord(f, 2) - mesh.GetTexCoord(f, 0)).length_squared();
302 float distSQ_13 = (mesh.GetTexCoord(f, 3) - mesh.GetTexCoord(f, 1)).length_squared();
303 bool quadDiagIs_02;
304 if (distSQ_02 != distSQ_13) {
305 quadDiagIs_02 = (distSQ_02 < distSQ_13);
306 }
307 else {
308 distSQ_02 = (mesh.GetPosition(f, 2) - mesh.GetPosition(f, 0)).length_squared();
309 distSQ_13 = (mesh.GetPosition(f, 3) - mesh.GetPosition(f, 1)).length_squared();
310 quadDiagIs_02 = !(distSQ_13 < distSQ_02);
311 }
312
313 if (quadDiagIs_02) {
314 triA.setVertices(0, 1, 2);
315 triB.setVertices(0, 2, 3);
316 }
317 else {
318 triA.setVertices(0, 1, 3);
319 triB.setVertices(1, 2, 3);
320 }
321 }
322
323 nrTSpaces += verts;
324 }
325 }
326
327 struct VertexHash {
329 uint operator()(const uint &k) const
330 {
331 return hash_float3x3(mikk->getPosition(k), mikk->getNormal(k), mikk->getTexCoord(k));
332 }
333 };
334
335 struct VertexEqual {
337 bool operator()(const uint &kA, const uint &kB) const
338 {
339 return mikk->getTexCoord(kA) == mikk->getTexCoord(kB) &&
340 mikk->getNormal(kA) == mikk->getNormal(kB) &&
341 mikk->getPosition(kA) == mikk->getPosition(kB);
342 }
343 };
344
345 /* Merge identical vertices.
346 * To find vertices with identical position, normal and texcoord, we calculate a hash of the 9
347 * values. Then, by sorting based on that hash, identical elements (having identical hashes) will
348 * be moved next to each other. Since there might be hash collisions, the elements of each block
349 * are then compared with each other and duplicates are merged.
350 */
351 template<bool isAtomic> void generateSharedVerticesIndexList_impl()
352 {
353 uint numVertices = nrTriangles * 3;
355 runParallel(0u, nrTriangles, [&](uint t) {
356 for (uint i = 0; i < 3; i++) {
357 auto res = set.emplace(triangles[t].vertices[i]);
358 if (!res.second) {
359 triangles[t].vertices[i] = res.first;
360 }
361 }
362 });
363 }
365 {
366 if (isParallel) {
368 }
369 else {
371 }
372 }
373
376
378 {
379 // Mark all degenerate triangles
380 totalTriangles = nrTriangles;
381 std::atomic<uint> degenTriangles(0);
382 runParallel(0u, totalTriangles, [&](uint t) {
383 const float3 p0 = getPosition(triangles[t].vertices[0]);
384 const float3 p1 = getPosition(triangles[t].vertices[1]);
385 const float3 p2 = getPosition(triangles[t].vertices[2]);
386 if (p0 == p1 || p0 == p2 || p1 == p2) { // degenerate
387 triangles[t].markDegenerate = true;
388 degenTriangles.fetch_add(1);
389 }
390 });
391 nrTriangles -= degenTriangles.load();
392
393 if (totalTriangles == nrTriangles) {
394 return;
395 }
396
397 // locate quads with only one good triangle
398 runParallel(0u, totalTriangles - 1, [&](uint t) {
399 Triangle &triangleA = triangles[t], &triangleB = triangles[t + 1];
400 if (triangleA.faceIdx != triangleB.faceIdx) {
401 /* Individual triangle, skip. */
402 return;
403 }
404 if (triangleA.markDegenerate != triangleB.markDegenerate) {
405 triangleA.quadOneDegenTri = true;
406 triangleB.quadOneDegenTri = true;
407 }
408 });
409
410 std::stable_partition(triangles.begin(), triangles.end(), [](const Triangle &tri) {
411 return !tri.markDegenerate;
412 });
413 }
414
416 {
417 if (nrTriangles == totalTriangles) {
418 return;
419 }
420
421 std::unordered_map<uint, uint> goodTriangleMap;
422 for (uint t = 0; t < nrTriangles; t++) {
423 for (uint i = 0; i < 3; i++) {
424 goodTriangleMap.emplace(triangles[t].vertices[i], pack_index(t, i));
425 }
426 }
427
428 // deal with degenerate triangles
429 // punishment for degenerate triangles is O(nrTriangles) extra memory.
430 for (uint t = nrTriangles; t < totalTriangles; t++) {
431 // degenerate triangles on a quad with one good triangle are skipped
432 // here but processed in the next loop
433 if (triangles[t].quadOneDegenTri) {
434 continue;
435 }
436
437 for (uint i = 0; i < 3; i++) {
438 const auto entry = goodTriangleMap.find(triangles[t].vertices[i]);
439 if (entry == goodTriangleMap.end()) {
440 // Matching vertex from good triangle is not found.
441 continue;
442 }
443
444 uint tSrc, iSrc;
445 unpack_index(tSrc, iSrc, entry->second);
446 const uint iSrcVert = triangles[tSrc].faceVertex[iSrc];
447 const uint iSrcOffs = triangles[tSrc].tSpaceIdx;
448 const uint iDstVert = triangles[t].faceVertex[i];
449 const uint iDstOffs = triangles[t].tSpaceIdx;
450 // copy tspace
451 tSpaces[iDstOffs + iDstVert] = tSpaces[iSrcOffs + iSrcVert];
452 }
453 }
454
455 // deal with degenerate quads with one good triangle
456 for (uint t = 0; t < nrTriangles; t++) {
457 // this triangle belongs to a quad where the
458 // other triangle is degenerate
459 if (!triangles[t].quadOneDegenTri) {
460 continue;
461 }
462 uint vertFlag = (1u << triangles[t].faceVertex[0]) | (1u << triangles[t].faceVertex[1]) |
463 (1u << triangles[t].faceVertex[2]);
464 uint missingFaceVertex = 0;
465 if ((vertFlag & 2) == 0) {
466 missingFaceVertex = 1;
467 }
468 else if ((vertFlag & 4) == 0) {
469 missingFaceVertex = 2;
470 }
471 else if ((vertFlag & 8) == 0) {
472 missingFaceVertex = 3;
473 }
474
475 uint faceIdx = triangles[t].faceIdx;
476 float3 dstP = mesh.GetPosition(faceIdx, missingFaceVertex);
477 bool found = false;
478 for (uint i = 0; i < 3; i++) {
479 const uint faceVertex = triangles[t].faceVertex[i];
480 const float3 srcP = mesh.GetPosition(faceIdx, faceVertex);
481 if (srcP == dstP) {
482 const uint offset = triangles[t].tSpaceIdx;
483 tSpaces[offset + missingFaceVertex] = tSpaces[offset + faceVertex];
484 found = true;
485 break;
486 }
487 }
488 assert(found);
489 (void)found;
490 }
491 }
492
495
496 // returns the texture area times 2
497 float calcTexArea(uint tri)
498 {
499 const float3 t1 = getTexCoord(triangles[tri].vertices[0]);
500 const float3 t2 = getTexCoord(triangles[tri].vertices[1]);
501 const float3 t3 = getTexCoord(triangles[tri].vertices[2]);
502
503 const float t21x = t2.x - t1.x;
504 const float t21y = t2.y - t1.y;
505 const float t31x = t3.x - t1.x;
506 const float t31y = t3.y - t1.y;
507
508 const float signedAreaSTx2 = t21x * t31y - t21y * t31x;
509 return fabsf(signedAreaSTx2);
510 }
511
513 {
514 // triangles[f].iFlag is cleared in generateInitialVerticesIndexList()
515 // which is called before this function.
516
517 // evaluate first order derivatives
518 runParallel(0u, nrTriangles, [&](uint t) {
519 Triangle &triangle = triangles[t];
520
521 // initial values
522 const float3 v1 = getPosition(triangle.vertices[0]);
523 const float3 v2 = getPosition(triangle.vertices[1]);
524 const float3 v3 = getPosition(triangle.vertices[2]);
525 const float3 t1 = getTexCoord(triangle.vertices[0]);
526 const float3 t2 = getTexCoord(triangle.vertices[1]);
527 const float3 t3 = getTexCoord(triangle.vertices[2]);
528
529 float t21x = t2.x - t1.x;
530 float t31x = t3.x - t1.x;
531 if (!has_uv()) {
532 /* Compute edge length in toroidal space, since the u generated by `map_to_sphere()` might
533 * go cross the seam. */
534 t21x -= floorf(t21x + 0.5f);
535 t31x -= floorf(t31x + 0.5f);
536 }
537
538 const float t21y = t2.y - t1.y;
539 const float t31y = t3.y - t1.y;
540 const float3 d1 = v2 - v1, d2 = v3 - v1;
541
542 const float signedAreaSTx2 = t21x * t31y - t21y * t31x;
543 const float3 vOs = (t31y * d1) - (t21y * d2); // eq 18
544 const float3 vOt = (-t31x * d1) + (t21x * d2); // eq 19
545
546 triangle.orientPreserving = (signedAreaSTx2 > 0);
547
548 if (not_zero(signedAreaSTx2)) {
549 const float lenOs2 = vOs.length_squared();
550 const float lenOt2 = vOt.length_squared();
551 const float fS = triangle.orientPreserving ? 1.0f : (-1.0f);
552 if (not_zero(lenOs2)) {
553 triangle.tangent = vOs * (fS / sqrtf(lenOs2));
554 }
555
556 // if this is a good triangle
557 if (not_zero(lenOs2) && not_zero(lenOt2)) {
558 triangle.groupWithAny = false;
559 }
560 }
561 });
562
563 // force otherwise healthy quads to a fixed orientation
564 runParallel(0u, nrTriangles - 1, [&](uint t) {
565 Triangle &triangleA = triangles[t], &triangleB = triangles[t + 1];
566 if (triangleA.faceIdx != triangleB.faceIdx) {
567 // this is not a quad
568 return;
569 }
570
571 // bad triangles should already have been removed by
572 // degenPrologue(), but just in case check that neither are degenerate
573 if (!(triangleA.markDegenerate || triangleB.markDegenerate)) {
574 // if this happens the quad has extremely bad mapping!!
575 if (triangleA.orientPreserving != triangleB.orientPreserving) {
576 bool chooseOrientFirstTri = false;
577 if (triangleB.groupWithAny) {
578 chooseOrientFirstTri = true;
579 }
580 else if (calcTexArea(t) >= calcTexArea(t + 1)) {
581 chooseOrientFirstTri = true;
582 }
583
584 // force match
585 const uint t0 = chooseOrientFirstTri ? t : (t + 1);
586 const uint t1 = chooseOrientFirstTri ? (t + 1) : t;
587 triangles[t1].orientPreserving = triangles[t0].orientPreserving;
588 }
589 }
590 });
591 }
592
595
597 struct Entry {
598 Entry(uint32_t key_, uint data_) : key(key_), data(data_) {}
599 uint key, data;
600 };
601 std::vector<Entry> entries;
602
604 {
605 entries.reserve(capacity);
606 }
607
609 {
610 /* Entries are added by iterating over t, so by using a stable sort,
611 * we don't have to compare based on t as well. */
612 {
613 std::vector<Entry> tempEntries(entries.size(), {0, 0});
614 radixsort(entries, tempEntries, [](const Entry &e) { return e.key; });
615 }
616
617 for (uint i = 0; i < entries.size(); i++) {
618 const Entry &a = entries[i];
619 uint tA, iA;
620 unpack_index(tA, iA, a.data);
621 Mikktspace<Mesh>::Triangle &triA = mikk->triangles[tA];
622
623 if (triA.neighbor[iA] != UNSET_ENTRY) {
624 continue;
625 }
626
627 uint i0A = triA.vertices[iA], i1A = triA.vertices[(iA != 2) ? (iA + 1) : 0];
628 for (uint j = i + 1; j < entries.size(); j++) {
629 const Entry &b = entries[j];
630 uint tB, iB;
631 unpack_index(tB, iB, b.data);
632 Mikktspace<Mesh>::Triangle &triB = mikk->triangles[tB];
633
634 if (b.key != a.key) {
635 break;
636 }
637
638 if (triB.neighbor[iB] != UNSET_ENTRY) {
639 continue;
640 }
641
642 uint i1B = triB.vertices[iB], i0B = triB.vertices[(iB != 2) ? (iB + 1) : 0];
643 if (i0A == i0B && i1A == i1B) {
644 triA.neighbor[iA] = tB;
645 triB.neighbor[iB] = tA;
646 break;
647 }
648 }
649 }
650 }
651 };
652
654 {
655 /* In order to parallelize the processing, we divide the vertices into shards.
656 * Since only vertex pairs with the same key will be checked, we can process
657 * shards independently as long as we ensure that all vertices with the same
658 * key go into the same shard.
659 * This is done by hashing the key to get the shard index of each vertex.
660 */
661 // TODO: Two-step filling that first counts and then fills? Could be parallel then.
662 uint targetNrShards = isParallel ? uint(4 * nrThreads) : 1;
663 uint nrShards = 1, hashShift = 32;
664 while (nrShards < targetNrShards) {
665 nrShards *= 2;
666 hashShift -= 1;
667 }
668
669 /* Reserve 25% extra to account for variation due to hashing. */
670 size_t reserveSize = size_t(double(3 * nrTriangles) * 1.25 / nrShards);
671 std::vector<NeighborShard> shards(nrShards, {reserveSize});
672
673 for (uint t = 0; t < nrTriangles; t++) {
674 Triangle &triangle = triangles[t];
675 for (uint i = 0; i < 3; i++) {
676 const uint i0 = triangle.vertices[i];
677 const uint i1 = triangle.vertices[(i != 2) ? (i + 1) : 0];
678 const uint high = std::max(i0, i1), low = std::min(i0, i1);
679 const uint hash = hash_uint3(high, low, 0);
680 /* TODO: Reusing the hash here means less hash space inside each shard.
681 * Computing a second hash with a different seed it probably not worth it? */
682 const uint shard = isParallel ? (hash >> hashShift) : 0;
683 shards[shard].entries.emplace_back(hash, pack_index(t, i));
684 }
685 }
686
687 runParallel(0u, nrShards, [&](uint s) { shards[s].buildNeighbors(this); });
688 }
689
692
693 void assignRecur(const uint t, uint groupId)
694 {
695 if (t == UNSET_ENTRY) {
696 return;
697 }
698
699 Triangle &triangle = triangles[t];
700 Group &group = groups[groupId];
701
702 // track down vertex
703 const uint vertRep = group.vertexRepresentative;
704 uint i = 3;
705 if (triangle.vertices[0] == vertRep) {
706 i = 0;
707 }
708 else if (triangle.vertices[1] == vertRep) {
709 i = 1;
710 }
711 else if (triangle.vertices[2] == vertRep) {
712 i = 2;
713 }
714 assert(i < 3);
715
716 // early out
717 if (triangle.group[i] != UNSET_ENTRY) {
718 return;
719 }
720
721 if (triangle.groupWithAny) {
722 // first to group with a group-with-anything triangle
723 // determines its orientation.
724 // This is the only existing order dependency in the code!!
725 if (triangle.group[0] == UNSET_ENTRY && triangle.group[1] == UNSET_ENTRY &&
726 triangle.group[2] == UNSET_ENTRY)
727 {
728 triangle.orientPreserving = group.orientPreserving;
729 }
730 }
731
732 if (triangle.orientPreserving != group.orientPreserving) {
733 return;
734 }
735
736 triangle.group[i] = groupId;
737
738 const uint t_L = triangle.neighbor[i];
739 const uint t_R = triangle.neighbor[i > 0 ? (i - 1) : 2];
740 assignRecur(t_L, groupId);
741 assignRecur(t_R, groupId);
742 }
743
745 {
746 /* NOTE: This could be parallelized by grouping all [t, i] pairs into
747 * shards by hash(triangles[t].vertices[i]). This way, each shard can be processed
748 * independently and in parallel.
749 * However, the `groupWithAny` logic needs special handling (e.g. lock a mutex when
750 * encountering a `groupWithAny` triangle, then sort it out, then unlock and proceed). */
751 for (uint t = 0; t < nrTriangles; t++) {
752 Triangle &triangle = triangles[t];
753 for (uint i = 0; i < 3; i++) {
754 // if not assigned to a group
755 if (triangle.groupWithAny || triangle.group[i] != UNSET_ENTRY) {
756 continue;
757 }
758
759 const uint newGroupId = uint(groups.size());
760 triangle.group[i] = newGroupId;
761
762 groups.emplace_back(triangle.vertices[i], bool(triangle.orientPreserving));
763
764 const uint t_L = triangle.neighbor[i];
765 const uint t_R = triangle.neighbor[i > 0 ? (i - 1) : 2];
766 assignRecur(t_L, newGroupId);
767 assignRecur(t_R, newGroupId);
768 }
769 }
770 }
771
774
775 template<bool atomic> void accumulateTSpaces(uint t)
776 {
777 const Triangle &triangle = triangles[t];
778 // only valid triangles get to add their contribution
779 if (triangle.groupWithAny) {
780 return;
781 }
782
783 /* TODO: Vectorize?
784 * Also: Could add special case for flat shading, when all normals are equal half of the fCos
785 * projections and two of the three tangent projections are unnecessary. */
786 std::array<float3, 3> n, p;
787 for (uint i = 0; i < 3; i++) {
788 n[i] = getNormal(triangle.vertices[i]);
789 p[i] = getPosition(triangle.vertices[i]);
790 }
791
792 std::array<float, 3> fCos = {dot(project(n[0], p[1] - p[0]), project(n[0], p[2] - p[0])),
793 dot(project(n[1], p[2] - p[1]), project(n[1], p[0] - p[1])),
794 dot(project(n[2], p[0] - p[2]), project(n[2], p[1] - p[2]))};
795
796 for (uint i = 0; i < 3; i++) {
797 uint groupId = triangle.group[i];
798 if (groupId != UNSET_ENTRY) {
799 float3 tangent = project(n[i], triangle.tangent) *
800 fast_acosf(std::clamp(fCos[i], -1.0f, 1.0f));
801 if constexpr (atomic) {
802 groups[groupId].accumulateTSpaceAtomic(tangent);
803 }
804 else {
805 groups[groupId].accumulateTSpace(tangent);
806 }
807 }
808 }
809 }
810
812 {
813 if (isParallel) {
814 runParallel(0u, nrTriangles, [&](uint t) { accumulateTSpaces<true>(t); });
815 }
816 else {
817 for (uint t = 0; t < nrTriangles; t++) {
819 }
820 }
821
822 /* TODO: Worth parallelizing? Probably not. */
823 for (Group &group : groups) {
824 group.normalizeTSpace();
825 }
826
827 tSpaces.resize(nrTSpaces);
828
829 for (uint t = 0; t < nrTriangles; t++) {
830 Triangle &triangle = triangles[t];
831 for (uint i = 0; i < 3; i++) {
832 uint groupId = triangle.group[i];
833 if (groupId == UNSET_ENTRY) {
834 continue;
835 }
836 const Group group = groups[groupId];
837 assert(triangle.orientPreserving == group.orientPreserving);
838
839 // output tspace
840 const uint offset = triangle.tSpaceIdx;
841 const uint faceVertex = triangle.faceVertex[i];
842 tSpaces[offset + faceVertex].accumulateGroup(group);
843 }
844 }
845 }
846};
847
848} // namespace mikk
int numVertices() const
void assignRecur(const uint t, uint groupId)
void generateSharedVerticesIndexList_impl()
float3 getPosition(uint vertexID)
void generateSharedVerticesIndexList()
void runParallel(uint start, uint end, F func)
void build4RuleGroups()
Mikktspace(Mesh &mesh_)
void generateInitialVerticesIndexList()
float3 getNormal(uint vertexID)
float calcTexArea(uint tri)
float3 getTexCoord(uint vertexID)
void accumulateTSpaces(uint t)
bool has_uv() const
uint hash_uint3(uint kx, uint ky, uint kz)
#define assert(assertion)
#define index(i)
#define capacity(const)
VecBase< float, D > normalize(VecOp< float, D >) RET
#define F
float dot(const float3 &a, const float3 &b)
bool not_zero(const float fX)
Definition mikk_util.hh:22
float3 project(const float3 &n, const float3 &v)
void radixsort(std::vector< T > &data, std::vector< T > &data2, KeyGetter getKey)
Definition mikk_util.hh:108
float fast_acosf(float x)
Definition mikk_util.hh:41
static constexpr uint UNSET_ENTRY
Definition mikktspace.hh:24
#define hash
Definition noise_c.cc:156
#define floorf
#define fabsf
#define sqrtf
Entry(uint32_t key_, uint data_)
std::vector< Entry > entries
void buildNeighbors(Mikktspace< Mesh > *mikk)
bool operator()(const uint &kA, const uint &kB) const
uint operator()(const uint &k) const
float length_squared() const
float3 normalize() const