139 uint nrTSpaces, nrFaces, nrTriangles, totalTriangles;
149 nrFaces = uint(mesh.GetNumFaces());
152 nrThreads = tbb::this_task_arena::max_concurrency();
153 isParallel = (nrThreads > 1) && (nrFaces > 10000);
162 if (nrTriangles == 0) {
176 if (nrTriangles == 0) {
178 tSpaces.resize(nrTSpaces);
202 for (uint f = 0; f < nrFaces; f++) {
203 const uint verts = mesh.GetNumVerticesOfFace(f);
204 if (verts != 3 && verts != 4) {
209 for (uint i = 0; i < verts; i++) {
210 const TSpace &tSpace = tSpaces[
index++];
211 mesh.SetTangentSpace(f, i, tSpace.tangent, tSpace.orientPreserving);
267 for (uint f = 0; f < nrFaces; f++) {
268 const uint verts = mesh.GetNumVerticesOfFace(f);
272 else if (verts == 4) {
277 triangles.reserve(nrTriangles);
280 for (uint f = 0; f < nrFaces; f++) {
281 const uint verts = mesh.GetNumVerticesOfFace(f);
282 if (verts != 3 && verts != 4) {
286 uint tA = uint(triangles.size());
287 triangles.emplace_back(f, nrTSpaces);
288 Triangle &triA = triangles[tA];
291 triA.setVertices(0, 1, 2);
294 uint tB = uint(triangles.size());
295 triangles.emplace_back(f, nrTSpaces);
296 Triangle &triB = triangles[tB];
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();
304 if (distSQ_02 != distSQ_13) {
305 quadDiagIs_02 = (distSQ_02 < distSQ_13);
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);
314 triA.setVertices(0, 1, 2);
315 triB.setVertices(0, 2, 3);
318 triA.setVertices(0, 1, 3);
319 triB.setVertices(1, 2, 3);
380 totalTriangles = nrTriangles;
381 std::atomic<uint> degenTriangles(0);
386 if (p0 == p1 || p0 == p2 || p1 == p2) {
387 triangles[t].markDegenerate =
true;
388 degenTriangles.fetch_add(1);
391 nrTriangles -= degenTriangles.load();
393 if (totalTriangles == nrTriangles) {
399 Triangle &triangleA = triangles[t], &triangleB = triangles[t + 1];
400 if (triangleA.faceIdx != triangleB.faceIdx) {
404 if (triangleA.markDegenerate != triangleB.markDegenerate) {
405 triangleA.quadOneDegenTri =
true;
406 triangleB.quadOneDegenTri =
true;
410 std::stable_partition(triangles.begin(), triangles.end(), [](
const Triangle &tri) {
411 return !tri.markDegenerate;
417 if (nrTriangles == totalTriangles) {
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));
430 for (uint t = nrTriangles; t < totalTriangles; t++) {
433 if (triangles[t].quadOneDegenTri) {
437 for (uint i = 0; i < 3; i++) {
438 const auto entry = goodTriangleMap.find(triangles[t].vertices[i]);
439 if (entry == goodTriangleMap.end()) {
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;
451 tSpaces[iDstOffs + iDstVert] = tSpaces[iSrcOffs + iSrcVert];
456 for (uint t = 0; t < nrTriangles; t++) {
459 if (!triangles[t].quadOneDegenTri) {
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;
468 else if ((vertFlag & 4) == 0) {
469 missingFaceVertex = 2;
471 else if ((vertFlag & 8) == 0) {
472 missingFaceVertex = 3;
475 uint faceIdx = triangles[t].faceIdx;
476 float3 dstP = mesh.GetPosition(faceIdx, missingFaceVertex);
478 for (uint i = 0; i < 3; i++) {
479 const uint faceVertex = triangles[t].faceVertex[i];
480 const float3 srcP = mesh.GetPosition(faceIdx, faceVertex);
482 const uint offset = triangles[t].tSpaceIdx;
483 tSpaces[offset + missingFaceVertex] = tSpaces[offset + faceVertex];
519 Triangle &triangle = triangles[t];
529 float t21x = t2.
x - t1.
x;
530 float t31x = t3.
x - t1.
x;
534 t21x -=
floorf(t21x + 0.5f);
535 t31x -=
floorf(t31x + 0.5f);
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;
542 const float signedAreaSTx2 = t21x * t31y - t21y * t31x;
543 const float3 vOs = (t31y * d1) - (t21y * d2);
544 const float3 vOt = (-t31x * d1) + (t21x * d2);
546 triangle.orientPreserving = (signedAreaSTx2 > 0);
551 const float fS = triangle.orientPreserving ? 1.0f : (-1.0f);
553 triangle.tangent = vOs * (fS /
sqrtf(lenOs2));
558 triangle.groupWithAny =
false;
565 Triangle &triangleA = triangles[t], &triangleB = triangles[t + 1];
566 if (triangleA.faceIdx != triangleB.faceIdx) {
573 if (!(triangleA.markDegenerate || triangleB.markDegenerate)) {
575 if (triangleA.orientPreserving != triangleB.orientPreserving) {
576 bool chooseOrientFirstTri =
false;
577 if (triangleB.groupWithAny) {
578 chooseOrientFirstTri =
true;
581 chooseOrientFirstTri =
true;
585 const uint t0 = chooseOrientFirstTri ? t : (t + 1);
586 const uint t1 = chooseOrientFirstTri ? (t + 1) : t;
587 triangles[t1].orientPreserving = triangles[t0].orientPreserving;
662 uint targetNrShards = isParallel ? uint(4 * nrThreads) : 1;
663 uint nrShards = 1, hashShift = 32;
664 while (nrShards < targetNrShards) {
670 size_t reserveSize = size_t(
double(3 * nrTriangles) * 1.25 / nrShards);
671 std::vector<NeighborShard> shards(nrShards, {reserveSize});
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);
682 const uint shard = isParallel ? (
hash >> hashShift) : 0;
683 shards[shard].entries.emplace_back(
hash, pack_index(t, i));
687 runParallel(0u, nrShards, [&](uint s) { shards[s].buildNeighbors(
this); });
699 Triangle &triangle = triangles[t];
700 Group &group = groups[groupId];
703 const uint vertRep = group.vertexRepresentative;
705 if (triangle.vertices[0] == vertRep) {
708 else if (triangle.vertices[1] == vertRep) {
711 else if (triangle.vertices[2] == vertRep) {
721 if (triangle.groupWithAny) {
728 triangle.orientPreserving = group.orientPreserving;
732 if (triangle.orientPreserving != group.orientPreserving) {
736 triangle.group[i] = groupId;
738 const uint t_L = triangle.neighbor[i];
739 const uint t_R = triangle.neighbor[i > 0 ? (i - 1) : 2];
751 for (uint t = 0; t < nrTriangles; t++) {
752 Triangle &triangle = triangles[t];
753 for (uint i = 0; i < 3; i++) {
755 if (triangle.groupWithAny || triangle.group[i] !=
UNSET_ENTRY) {
759 const uint newGroupId = uint(groups.size());
760 triangle.group[i] = newGroupId;
762 groups.emplace_back(triangle.vertices[i],
bool(triangle.orientPreserving));
764 const uint t_L = triangle.neighbor[i];
765 const uint t_R = triangle.neighbor[i > 0 ? (i - 1) : 2];
777 const Triangle &triangle = triangles[t];
779 if (triangle.groupWithAny) {
786 std::array<float3, 3> n, p;
787 for (uint i = 0; i < 3; i++) {
792 std::array<float, 3> fCos = {
dot(
project(n[0], p[1] - p[0]),
project(n[0], p[2] - p[0])),
796 for (uint i = 0; i < 3; i++) {
797 uint groupId = triangle.group[i];
801 if constexpr (atomic) {
802 groups[groupId].accumulateTSpaceAtomic(tangent);
805 groups[groupId].accumulateTSpace(tangent);
817 for (uint t = 0; t < nrTriangles; t++) {
823 for (Group &group : groups) {
824 group.normalizeTSpace();
827 tSpaces.resize(nrTSpaces);
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];
836 const Group group = groups[groupId];
837 assert(triangle.orientPreserving == group.orientPreserving);
840 const uint offset = triangle.tSpaceIdx;
841 const uint faceVertex = triangle.faceVertex[i];
842 tSpaces[offset + faceVertex].accumulateGroup(group);