Free, open-source 3D sculpting for Linux, macOS and Windows: dense meshes, remeshing, painting, built-in AI (image/text to 3D), Send to Unreal, game-ready LODs, Gaussian splats and OpenUSD.
C++ 3d3d-sculptingcppdear-imguidigital-sculptingfbxgame-developmentgaussian-splattinggltfimage-to-3dmcpopenglopenusdsculptingtext-to-3dunreal-engine
// SculptForge - open source digital sculpting
// SPDX-License-Identifier: GPL-3.0-or-later
#include "core/Uv.h"
#include "core/Mesh.h"
#include "core/ThreadPool.h"
#include "core/UvInternal.h"
#include <algorithm>
#include <cmath>
#include <limits>
#include <map>
#include <queue>
#include <sstream>
namespace sf {
using namespace uvdetail;
namespace uvdetail {
std::vector<glm::vec2> convexHull(std::vector<glm::vec2> pts) {
std::sort(pts.begin(), pts.end(), [](glm::vec2 a, glm::vec2 b) { return a.x < b.x || (a.x == b.x && a.y < b.y); });
pts.erase(std::unique(pts.begin(), pts.end()), pts.end());
if (pts.size() < 3) return pts;
std::vector<glm::vec2> h(pts.size() * 2);
size_t k = 0;
for (size_t i = 0; i < pts.size(); ++i) {
while (k >= 2 && cross2(h[k - 1] - h[k - 2], pts[i] - h[k - 2]) <= 0.0f) --k;
h[k++] = pts[i];
}
for (size_t i = pts.size() - 1, lo = k + 1; i-- > 0;) {
while (k >= lo && cross2(h[k - 1] - h[k - 2], pts[i] - h[k - 2]) <= 0.0f) --k;
h[k++] = pts[i];
}
h.resize(k - 1);
return h;
}
float minAreaRectAngle(const std::vector<glm::vec2>& pts) {
const std::vector<glm::vec2> h = convexHull(pts);
if (h.size() < 3) {
if (h.size() == 2) return -std::atan2(h[1].y - h[0].y, h[1].x - h[0].x);
return 0.0f;
}
// Rotating calipers: the smallest box has a side on a hull edge.
float bestArea = std::numeric_limits<float>::max(), best = 0.0f;
for (size_t i = 0; i < h.size(); ++i) {
const glm::vec2 e = h[(i + 1) % h.size()] - h[i];
const float len = glm::length(e);
if (len <= 0.0f) continue;
const float c = e.x / len, s = -e.y / len; // rotation by -angle(e)
glm::vec2 lo(std::numeric_limits<float>::max()), hi(std::numeric_limits<float>::lowest());
for (const glm::vec2& p : h) {
const glm::vec2 q = rotate(p, c, s);
lo = glm::min(lo, q);
hi = glm::max(hi, q);
}
const glm::vec2 d = hi - lo;
const float area = d.x * d.y;
if (area < bestArea * 0.9999f) {
bestArea = area;
best = std::atan2(s, c);
if (d.y > d.x) best += 1.5707963f; // long side along u
}
}
return best;
}
void islandCorners(const UvTopology& topo, std::vector<uint32_t>& offsets, std::vector<uint32_t>& corners) {
offsets.assign(topo.islandCount + 1, 0);
for (uint32_t i = 0; i < topo.islandCount; ++i)
offsets[i + 1] = offsets[i] + 3 * (topo.islandOffsets[i + 1] - topo.islandOffsets[i]);
corners.resize(offsets.back());
poolFor(topo.islandCount, [&](size_t b, size_t e) {
for (size_t i = b; i < e; ++i) {
uint32_t at = offsets[i];
for (uint32_t k = topo.islandOffsets[i]; k < topo.islandOffsets[i + 1]; ++k) {
const uint32_t t = topo.islandTriangles[k];
for (uint32_t j = 0; j < 3; ++j) corners[at++] = t * 3 + j;
}
}
}, 64);
}
} // namespace uvdetail
int udimTile(const glm::vec2& uv) {
const int u = std::clamp(int(std::floor(uv.x)), 0, 9);
const int v = std::max(int(std::floor(uv.y)), 0);
return 1001 + u + 10 * v;
}
glm::vec2 udimOrigin(int tile) {
const int i = std::max(tile - 1001, 0);
return {float(i % 10), float(i / 10)};
}
std::vector<uint32_t> cornerTwins(const Mesh& m) {
const size_t nt = m.triangleCount(), nv = m.vertexCount();
std::vector<uint32_t> twin(nt * 3, kNoCorner);
if (nt == 0) return twin;
// Corners bucketed by the lower vertex of their edge (a counting sort), then matched within each bucket.
std::vector<uint32_t> offsets(nv + 1, 0);
auto lower = [&](uint32_t c) {
const glm::uvec3& t = m.triangles[c / 3];
return std::min(t[c % 3], t[(c % 3 + 1) % 3]);
};
for (uint32_t c = 0; c < nt * 3; ++c) ++offsets[lower(c) + 1];
for (size_t v = 0; v < nv; ++v) offsets[v + 1] += offsets[v];
std::vector<uint32_t> fill(offsets.begin(), offsets.end() - 1), list(nt * 3);
for (uint32_t c = 0; c < nt * 3; ++c) list[fill[lower(c)]++] = c;
poolFor(nv, [&](size_t b, size_t e) {
for (size_t v = b; v < e; ++v) {
const uint32_t* first = list.data() + offsets[v];
const uint32_t n = offsets[v + 1] - offsets[v];
for (uint32_t i = 0; i < n; ++i) {
const uint32_t c = first[i];
const glm::uvec3& tc = m.triangles[c / 3];
const uint32_t a = tc[c % 3], bb = tc[(c % 3 + 1) % 3];
uint32_t match = kNoCorner, same = 0;
for (uint32_t j = 0; j < n; ++j) {
if (j == i) continue;
const uint32_t d = first[j];
const glm::uvec3& td = m.triangles[d / 3];
const uint32_t da = td[d % 3], db = td[(d % 3 + 1) % 3];
if (da == bb && db == a) {
match = match == kNoCorner ? d : kNoCorner - 1; // two opposite: non-manifold
} else if (da == a && db == bb) {
++same;
}
}
twin[c] = (same == 0 && match < kNoCorner - 1) ? match : kNoCorner;
}
}
}, 1 << 12);
// Keep only mutual pairs.
for (uint32_t c = 0; c < nt * 3; ++c)
if (twin[c] != kNoCorner && twin[twin[c]] != c) twin[c] = kNoCorner;
return twin;
}
UvTopology buildUvTopology(const Mesh& m, std::vector<uint32_t> twin) {
UvTopology topo;
const size_t nt = m.triangleCount(), nc = nt * 3;
if (twin.size() != nc) twin = cornerTwins(m);
topo.twin = std::move(twin);
topo.border.assign(nc, 1);
const bool uvs = m.uvs.size() == nc;
const bool flags = m.uvFlags.size() == nc;
poolFor(nc, [&](size_t b, size_t e) {
for (size_t c = b; c < e; ++c) {
const uint32_t d = topo.twin[c];
if (d == kNoCorner) continue;
if (flags && ((m.uvFlags[c] | m.uvFlags[d]) & kUvSeam)) continue;
if (uvs && (m.uvs[c] != m.uvs[cornerNext(d)] || m.uvs[cornerNext(uint32_t(c))] != m.uvs[d])) continue;
topo.border[c] = 0;
}
}, 1 << 15);
DisjointSets corners(nc), tris(nt);
for (uint32_t c = 0; c < nc; ++c) {
if (topo.border[c]) continue;
const uint32_t d = topo.twin[c];
if (d < c) continue;
corners.unite(c, cornerNext(d));
corners.unite(cornerNext(c), d);
tris.unite(c / 3, d / 3);
}
topo.uvVertexCount = corners.labels(topo.uvVertex);
topo.islandCount = tris.labels(topo.island);
topo.islandOffsets.assign(topo.islandCount + 1, 0);
for (uint32_t t = 0; t < nt; ++t) ++topo.islandOffsets[topo.island[t] + 1];
for (uint32_t i = 0; i < topo.islandCount; ++i) topo.islandOffsets[i + 1] += topo.islandOffsets[i];
std::vector<uint32_t> at(topo.islandOffsets.begin(), topo.islandOffsets.end() - 1);
topo.islandTriangles.resize(nt);
for (uint32_t t = 0; t < nt; ++t) topo.islandTriangles[at[topo.island[t]]++] = t;
return topo;
}
// ---------------------------------------------------------------------------------------------------------------
// Measures
namespace {
float area3(const Mesh& m, uint32_t t) {
const glm::uvec3& tri = m.triangles[t];
return 0.5f * glm::length(glm::cross(m.positions[tri.y] - m.positions[tri.x], m.positions[tri.z] - m.positions[tri.x]));
}
float signedAreaUv(const Mesh& m, uint32_t t) {
const glm::vec2* u = m.uvs.data() + size_t(t) * 3;
return 0.5f * cross2(u[1] - u[0], u[2] - u[0]);
}
} // namespace
void uvTriangleDensity(const Mesh& m, int resolution, std::vector<float>& out) {
const size_t nt = m.triangleCount();
out.assign(nt, 0.0f);
if (m.uvs.size() != nt * 3) return;
poolFor(nt, [&](size_t b, size_t e) {
for (size_t t = b; t < e; ++t) {
const float a = area3(m, uint32_t(t));
out[t] = a > 0.0f ? std::sqrt(std::abs(signedAreaUv(m, uint32_t(t))) / a) * float(resolution) : 0.0f;
}
}, 1 << 14);
}
std::vector<float> uvIslandDensity(const Mesh& m, const UvTopology& topo, int resolution) {
std::vector<float> out(topo.islandCount, 0.0f);
if (m.uvs.size() != m.triangleCount() * 3) return out;
poolFor(topo.islandCount, [&](size_t b, size_t e) {
for (size_t i = b; i < e; ++i) {
double a = 0.0, u = 0.0;
for (uint32_t k = topo.islandOffsets[i]; k < topo.islandOffsets[i + 1]; ++k) {
const uint32_t t = topo.islandTriangles[k];
a += area3(m, t);
u += std::abs(signedAreaUv(m, t));
}
out[i] = a > 0.0 ? float(std::sqrt(u / a) * resolution) : 0.0f;
}
}, 64);
return out;
}
float uvMeshDensity(const Mesh& m, int resolution) {
const size_t nt = m.triangleCount();
if (m.uvs.size() != nt * 3 || nt == 0) return 0.0f;
double a = 0.0, u = 0.0;
for (uint32_t t = 0; t < nt; ++t) {
a += area3(m, t);
u += std::abs(signedAreaUv(m, t));
}
return a > 0.0 ? float(std::sqrt(u / a) * resolution) : 0.0f;
}
namespace {
// Singular values (s1 >= s2) and orientation of triangle t's map from its surface to UV space.
bool triangleJacobian(const Mesh& m, uint32_t t, float& s1, float& s2, bool& flipped) {
const glm::uvec3& tri = m.triangles[t];
const glm::vec3 e1 = m.positions[tri.y] - m.positions[tri.x], e2 = m.positions[tri.z] - m.positions[tri.x];
const float l1 = glm::length(e1);
const glm::vec3 n = glm::cross(e1, e2);
const float nl = glm::length(n);
if (l1 <= 0.0f || nl <= 0.0f) return false;
const glm::vec3 x = e1 / l1, y = glm::cross(n / nl, x);
// Surface triangle in its plane: (0,0), (l1,0), (q2x,q2y).
const float q2x = glm::dot(e2, x), q2y = glm::dot(e2, y);
const glm::vec2* u = m.uvs.data() + size_t(t) * 3;
const glm::vec2 d1 = u[1] - u[0], d2 = u[2] - u[0];
// J * [l1 q2x; 0 q2y] = [d1 d2] -> J = [d1 d2] * inverse.
if (std::abs(q2y) <= 0.0f) return false;
const glm::vec2 c0 = d1 / l1; // J's first column
const glm::vec2 c1 = (d2 - c0 * q2x) / q2y; // J's second column
const float a = c0.x, b = c1.x, c = c0.y, d = c1.y; // J = [a b; c d]
const float E = (a + d) * 0.5f, F = (a - d) * 0.5f, G = (c + b) * 0.5f, H = (c - b) * 0.5f;
const float Q = std::sqrt(E * E + H * H), R = std::sqrt(F * F + G * G);
s1 = Q + R;
s2 = std::abs(Q - R);
flipped = (a * d - b * c) < 0.0f;
if (!std::isfinite(s1) || !std::isfinite(s2)) return false; // (a sliver: no meaningful stretch)
return true;
}
} // namespace
void uvTriangleStretch(const Mesh& m, std::vector<float>& out) {
const size_t nt = m.triangleCount();
out.assign(nt, 0.0f);
if (m.uvs.size() != nt * 3 || nt == 0) return;
// Measured against each island's own scale, so islands packed smaller or larger don't count as stretched; and
// against its own sense, so an island laid out mirrored as a whole is fine (only triangles folded over the
// rest of their island count as flipped).
const UvTopology topo = buildUvTopology(m);
std::vector<float> scale(topo.islandCount, 0.0f);
std::vector<uint8_t> mirrored(topo.islandCount, 0);
poolFor(topo.islandCount, [&](size_t b, size_t e) {
for (size_t i = b; i < e; ++i) {
double a = 0.0, u = 0.0, sense = 0.0;
for (uint32_t k = topo.islandOffsets[i]; k < topo.islandOffsets[i + 1]; ++k) {
const uint32_t t = topo.islandTriangles[k];
const float su = signedAreaUv(m, t);
a += area3(m, t);
u += std::abs(su);
sense += su;
}
scale[i] = a > 0.0 ? float(std::sqrt(u / a)) : 0.0f;
mirrored[i] = sense < 0.0;
}
}, 64);
poolFor(nt, [&](size_t b, size_t e) {
for (size_t t = b; t < e; ++t) {
float s1 = 0, s2 = 0;
bool flipped = false;
const uint32_t i = topo.island[t];
const float s = scale[i];
if (s <= 0.0f || !triangleJacobian(m, uint32_t(t), s1, s2, flipped)) continue;
out[t] = flipped != bool(mirrored[i]) ? -1.0f
: std::log2(std::max(std::max(s1 / s, 1e-6f), s / std::max(s2, 1e-6f * s)));
}
}, 1 << 14);
}
UvStretchCache uvStretchCache(const Mesh& m, const UvTopology& topo) {
UvStretchCache cache;
cache.scale.assign(topo.islandCount, 0.0f);
cache.mirrored.assign(topo.islandCount, 0);
if (m.uvs.size() != m.triangleCount() * 3) return cache;
poolFor(topo.islandCount, [&](size_t b, size_t e) {
for (size_t i = b; i < e; ++i) {
double a = 0.0, u = 0.0, sense = 0.0;
for (uint32_t k = topo.islandOffsets[i]; k < topo.islandOffsets[i + 1]; ++k) {
const uint32_t t = topo.islandTriangles[k];
const float su = signedAreaUv(m, t);
a += area3(m, t);
u += std::abs(su);
sense += su;
}
cache.scale[i] = a > 0.0 ? float(std::sqrt(u / a)) : 0.0f;
cache.mirrored[i] = sense < 0.0;
}
}, 64);
return cache;
}
float uvTriangleStretchAt(const Mesh& m, uint32_t t, const UvTopology& topo, const UvStretchCache& cache) {
float s1 = 0, s2 = 0;
bool flipped = false;
const uint32_t i = topo.island[t];
const float s = cache.scale[i];
if (s <= 0.0f || !triangleJacobian(m, t, s1, s2, flipped)) return 0.0f;
if (flipped != bool(cache.mirrored[i])) return -1.0f;
return std::log2(std::max(std::max(s1 / s, 1e-6f), s / std::max(s2, 1e-6f * s)));
}
UvStretchStats uvStretchStats(const Mesh& m) {
UvStretchStats st;
std::vector<float> s;
uvTriangleStretch(m, s);
double wsum = 0.0, sum = 0.0, flipped = 0.0;
for (uint32_t t = 0; t < s.size(); ++t) {
const double w = std::abs(signedAreaUv(m, t));
wsum += w;
if (s[t] < 0.0f) {
flipped += w;
continue;
}
sum += w * s[t];
st.worst = std::max(st.worst, s[t]);
}
if (wsum > 0.0) {
st.mean = float(sum / wsum);
st.flipped = float(flipped / wsum);
}
return st;
}
glm::vec3 uvHeatColor(float x) {
x = std::clamp(x, -1.0f, 1.0f);
const glm::vec3 blue(0.18f, 0.42f, 0.95f), green(0.25f, 0.78f, 0.42f), yellow(0.98f, 0.82f, 0.25f), red(0.93f, 0.26f, 0.22f);
if (x < 0.0f) return glm::mix(green, blue, -x);
if (x < 0.5f) return glm::mix(green, yellow, x * 2.0f);
return glm::mix(yellow, red, (x - 0.5f) * 2.0f);
}
// ---------------------------------------------------------------------------------------------------------------
// Selection
const char* uvSelectModeId(UvSelectMode mode) {
switch (mode) {
case UvSelectMode::Vertex: return "vertex";
case UvSelectMode::Edge: return "edge";
case UvSelectMode::Face: return "face";
case UvSelectMode::Island: return "island";
}
return "island";
}
bool parseUvSelectMode(const std::string& id, UvSelectMode& mode) {
for (UvSelectMode m : {UvSelectMode::Vertex, UvSelectMode::Edge, UvSelectMode::Face, UvSelectMode::Island})
if (id == uvSelectModeId(m) || id == std::string(uvSelectModeId(m)) + "s") {
mode = m;
return true;
}
return false;
}
bool UvSelection::valid(const Mesh& m) const {
const bool faceMode = mode == UvSelectMode::Face || mode == UvSelectMode::Island;
return faceMode ? faces.size() == m.triangleCount() : corners.size() == m.triangleCount() * 3;
}
size_t UvSelection::count() const {
const bool faceMode = mode == UvSelectMode::Face || mode == UvSelectMode::Island;
const std::vector<uint8_t>& v = faceMode ? faces : corners;
return size_t(std::count_if(v.begin(), v.end(), [](uint8_t x) { return x != 0; }));
}
namespace {
// Every corner of every UV vertex marked in `hit` (per UV vertex).
std::vector<uint32_t> cornersOfUvVertices(const UvTopology& topo, const std::vector<uint8_t>& hit) {
std::vector<uint32_t> out;
for (uint32_t c = 0; c < topo.uvVertex.size(); ++c)
if (hit[topo.uvVertex[c]]) out.push_back(c);
return out;
}
} // namespace
std::vector<uint32_t> uvSelectedCorners(const Mesh& m, const UvTopology& topo, const UvSelection& sel) {
const size_t nc = m.triangleCount() * 3;
if (!sel.valid(m) || topo.uvVertex.size() != nc) return {};
std::vector<uint8_t> hit(topo.uvVertexCount, 0);
switch (sel.mode) {
case UvSelectMode::Face:
case UvSelectMode::Island:
for (uint32_t t = 0; t < sel.faces.size(); ++t)
if (sel.faces[t])
for (uint32_t j = 0; j < 3; ++j) hit[topo.uvVertex[t * 3 + j]] = 1;
break;
case UvSelectMode::Vertex:
for (uint32_t c = 0; c < nc; ++c)
if (sel.corners[c]) hit[topo.uvVertex[c]] = 1;
break;
case UvSelectMode::Edge:
for (uint32_t c = 0; c < nc; ++c)
if (sel.corners[c]) hit[topo.uvVertex[c]] = hit[topo.uvVertex[cornerNext(c)]] = 1;
break;
}
return cornersOfUvVertices(topo, hit);
}
std::vector<uint8_t> uvSelectedIslands(const Mesh& m, const UvTopology& topo, const UvSelection& sel, bool allIfEmpty) {
std::vector<uint8_t> out(topo.islandCount, 0);
if (sel.valid(m)) {
if (sel.mode == UvSelectMode::Face || sel.mode == UvSelectMode::Island) {
for (uint32_t t = 0; t < sel.faces.size(); ++t)
if (sel.faces[t]) out[topo.island[t]] = 1;
} else {
for (uint32_t c = 0; c < sel.corners.size(); ++c)
if (sel.corners[c]) out[topo.island[c / 3]] = 1;
}
}
if (allIfEmpty && std::find(out.begin(), out.end(), uint8_t(1)) == out.end()) std::fill(out.begin(), out.end(), uint8_t(1));
return out;
}
void uvConvertSelection(const Mesh& m, const UvTopology& topo, UvSelection& sel, UvSelectMode to) {
const size_t nt = m.triangleCount(), nc = nt * 3;
const bool fromFaces = sel.mode == UvSelectMode::Face || sel.mode == UvSelectMode::Island;
const bool toFaces = to == UvSelectMode::Face || to == UvSelectMode::Island;
if (!sel.valid(m)) {
sel.clear();
sel.mode = to;
return;
}
if (fromFaces && toFaces) {
if (to == UvSelectMode::Island) {
const std::vector<uint8_t> isl = uvSelectedIslands(m, topo, sel, false);
for (uint32_t t = 0; t < nt; ++t) sel.faces[t] = isl[topo.island[t]];
}
sel.mode = to;
return;
}
if (fromFaces) { // faces -> their corners (vertex) or their edges (edge)
std::vector<uint8_t> corners(nc, 0);
if (to == UvSelectMode::Edge) {
for (uint32_t t = 0; t < nt; ++t)
if (sel.faces[t]) corners[t * 3] = corners[t * 3 + 1] = corners[t * 3 + 2] = 1;
} else {
for (uint32_t c : uvSelectedCorners(m, topo, sel)) corners[c] = 1;
}
sel.corners = std::move(corners);
std::vector<uint8_t>().swap(sel.faces);
sel.mode = to;
return;
}
// Corners -> faces whose three UV vertices are all touched (edge mode: their edges' ends).
std::vector<uint8_t> hit(topo.uvVertexCount, 0);
for (uint32_t c = 0; c < nc; ++c)
if (sel.corners[c]) {
hit[topo.uvVertex[c]] = 1;
if (sel.mode == UvSelectMode::Edge) hit[topo.uvVertex[cornerNext(c)]] = 1;
}
if (toFaces) {
sel.faces.assign(nt, 0);
for (uint32_t t = 0; t < nt; ++t)
sel.faces[t] = hit[topo.uvVertex[t * 3]] && hit[topo.uvVertex[t * 3 + 1]] && hit[topo.uvVertex[t * 3 + 2]];
std::vector<uint8_t>().swap(sel.corners);
sel.mode = UvSelectMode::Face;
if (to == UvSelectMode::Island) uvConvertSelection(m, topo, sel, to);
return;
}
std::vector<uint8_t> corners(nc, 0);
if (to == UvSelectMode::Vertex) {
for (uint32_t c = 0; c < nc; ++c) corners[c] = hit[topo.uvVertex[c]];
} else { // vertex -> edge: edges with both ends touched
for (uint32_t c = 0; c < nc; ++c) corners[c] = hit[topo.uvVertex[c]] && hit[topo.uvVertex[cornerNext(c)]];
}
sel.corners = std::move(corners);
sel.mode = to;
}
void uvFacesInRect(const Mesh& m, glm::vec2 lo, glm::vec2 hi, bool touch, std::vector<uint32_t>& out) {
out.clear();
const size_t nt = m.triangleCount();
if (m.uvs.size() != nt * 3) return;
const size_t block = 1 << 14, blocks = (nt + block - 1) / block;
std::vector<std::vector<uint32_t>> parts(blocks);
poolFor(nt, [&](size_t b, size_t e) {
std::vector<uint32_t>& part = parts[b / block];
for (size_t t = b; t < e; ++t) {
const glm::vec2* u = m.uvs.data() + t * 3;
if (m.triangleHidden(uint32_t(t))) continue;
const glm::vec2 tlo = glm::min(u[0], glm::min(u[1], u[2])), thi = glm::max(u[0], glm::max(u[1], u[2]));
const bool inside = touch ? (tlo.x <= hi.x && thi.x >= lo.x && tlo.y <= hi.y && thi.y >= lo.y)
: (tlo.x >= lo.x && thi.x <= hi.x && tlo.y >= lo.y && thi.y <= hi.y);
if (inside) part.push_back(uint32_t(t));
}
}, block);
for (auto& p : parts) out.insert(out.end(), p.begin(), p.end());
}
// ---------------------------------------------------------------------------------------------------------------
// Editing
void uvTransform(std::vector<glm::vec2>& uvs, const std::vector<uint32_t>& corners, const glm::mat2& mat, glm::vec2 pivot,
glm::vec2 offset) {
poolFor(corners.size(), [&](size_t b, size_t e) {
for (size_t i = b; i < e; ++i) {
glm::vec2& p = uvs[corners[i]];
p = mat * (p - pivot) + pivot + offset;
}
}, 1 << 15);
}
glm::vec2 uvCenter(const std::vector<glm::vec2>& uvs, const std::vector<uint32_t>& corners) {
if (corners.empty()) return glm::vec2(0.5f);
glm::vec2 lo(std::numeric_limits<float>::max()), hi(std::numeric_limits<float>::lowest());
for (uint32_t c : corners) {
lo = glm::min(lo, uvs[c]);
hi = glm::max(hi, uvs[c]);
}
return (lo + hi) * 0.5f;
}
namespace {
std::vector<uint8_t>& ensureFlags(Mesh& m) {
if (m.uvFlags.size() != m.triangleCount() * 3) m.uvFlags.assign(m.triangleCount() * 3, 0);
return m.uvFlags;
}
void dropEmptyFlags(Mesh& m) {
if (std::all_of(m.uvFlags.begin(), m.uvFlags.end(), [](uint8_t f) { return f == 0; })) std::vector<uint8_t>().swap(m.uvFlags);
}
} // namespace
void uvSetSeams(Mesh& m, const std::vector<uint32_t>& twin, const std::vector<uint32_t>& corners, bool on) {
std::vector<uint8_t>& f = ensureFlags(m);
for (uint32_t c : corners) {
if (c >= f.size()) continue;
const uint32_t d = c < twin.size() ? twin[c] : kNoCorner;
if (on) {
f[c] |= kUvSeam;
if (d != kNoCorner) f[d] |= kUvSeam;
} else {
f[c] &= uint8_t(~kUvSeam);
if (d != kNoCorner) f[d] &= uint8_t(~kUvSeam);
}
}
dropEmptyFlags(m);
m.facesDirty = true;
}
size_t uvSeamsFromFaceGroups(Mesh& m, const std::vector<uint32_t>& twin) {
std::vector<uint32_t> cut;
for (uint32_t c = 0; c < twin.size(); ++c)
if (twin[c] != kNoCorner && twin[c] > c && m.facegroupAt(c / 3) != m.facegroupAt(twin[c] / 3)) cut.push_back(c);
uvSetSeams(m, twin, cut, true);
return cut.size();
}
size_t uvSeamsFromIslands(Mesh& m, const UvTopology& topo) {
std::vector<uint32_t> cut;
for (uint32_t c = 0; c < topo.twin.size(); ++c)
if (topo.border[c] && topo.twin[c] != kNoCorner && topo.twin[c] > c) cut.push_back(c);
uvSetSeams(m, topo.twin, cut, true);
return cut.size();
}
size_t uvSeamsFromAngle(Mesh& m, const std::vector<uint32_t>& twin, float degrees) {
const float cosLimit = std::cos(glm::radians(std::clamp(degrees, 0.0f, 180.0f)));
auto normal = [&](uint32_t t) {
const glm::uvec3& tri = m.triangles[t];
const glm::vec3 n = glm::cross(m.positions[tri.y] - m.positions[tri.x], m.positions[tri.z] - m.positions[tri.x]);
const float l = glm::length(n);
return l > 0.0f ? n / l : glm::vec3(0.0f);
};
std::vector<uint32_t> cut;
for (uint32_t c = 0; c < twin.size(); ++c)
if (twin[c] != kNoCorner && twin[c] > c && glm::dot(normal(c / 3), normal(twin[c] / 3)) < cosLimit) cut.push_back(c);
uvSetSeams(m, twin, cut, true);
return cut.size();
}
size_t uvSeamCount(const Mesh& m) {
if (m.uvFlags.size() != m.triangleCount() * 3) return 0;
size_t n = 0;
for (uint8_t f : m.uvFlags) n += (f & kUvSeam) != 0;
return (n + 1) / 2; // (open edges are marked on one side only)
}
void uvClearSeams(Mesh& m) {
if (m.uvFlags.empty()) return;
for (uint8_t& f : m.uvFlags) f &= uint8_t(~kUvSeam);
dropEmptyFlags(m);
m.facesDirty = true;
}
std::vector<uint32_t> uvFaceSetBorder(const Mesh& m, const std::vector<uint32_t>& twin, const std::vector<uint8_t>& faces) {
std::vector<uint32_t> out;
if (faces.size() != m.triangleCount()) return out;
for (uint32_t c = 0; c < twin.size(); ++c) {
if (!faces[c / 3]) continue;
const uint32_t d = twin[c];
if (d != kNoCorner && !faces[d / 3]) out.push_back(c);
}
return out;
}
std::vector<uint32_t> uvEdgePath(const Mesh& m, uint32_t a, uint32_t b) {
const size_t nv = m.vertexCount();
if (a >= nv || b >= nv || a == b) return {};
std::vector<float> dist(nv, std::numeric_limits<float>::max());
std::vector<uint32_t> from(nv, ~0u);
using Item = std::pair<float, uint32_t>;
std::priority_queue<Item, std::vector<Item>, std::greater<>> queue;
dist[a] = 0.0f;
queue.push({0.0f, a});
while (!queue.empty()) {
const auto [d, v] = queue.top();
queue.pop();
if (d > dist[v]) continue;
if (v == b) break;
for (uint32_t w : m.neighbors(v)) {
const float nd = d + glm::length(m.positions[w] - m.positions[v]);
if (nd < dist[w]) {
dist[w] = nd;
from[w] = v;
queue.push({nd, w});
}
}
}
if (from[b] == ~0u) return {};
std::vector<uint32_t> out;
for (uint32_t v = b; v != a; v = from[v]) {
const uint32_t u = from[v];
// A corner that starts the edge u -> v or v -> u.
uint32_t corner = kNoCorner;
for (uint32_t t : m.vertexTriangles(u)) {
for (uint32_t j = 0; j < 3 && corner == kNoCorner; ++j) {
const uint32_t x = m.triangles[t][j], y = m.triangles[t][(j + 1) % 3];
if ((x == u && y == v) || (x == v && y == u)) corner = t * 3 + j;
}
if (corner != kNoCorner) break;
}
if (corner != kNoCorner) out.push_back(corner);
}
std::reverse(out.begin(), out.end());
return out;
}
void uvSetPins(Mesh& m, const std::vector<uint32_t>& corners, bool on) {
std::vector<uint8_t>& f = ensureFlags(m);
for (uint32_t c : corners) {
if (c >= f.size()) continue;
if (on) f[c] |= kUvPin;
else f[c] &= uint8_t(~kUvPin);
}
dropEmptyFlags(m);
}
size_t uvWeld(Mesh& m, const UvTopology& topo, const std::vector<uint32_t>& corners) {
const size_t nc = m.triangleCount() * 3;
if (m.uvs.size() != nc || corners.empty()) return 0;
std::vector<uint8_t> inSet(nc, 0);
for (uint32_t c : corners) inSet[c] = 1;
auto vert = [&](uint32_t c) { return m.triangles[c / 3][c % 3]; };
// Corners in the set meet across an edge whose both ends are in the set: those become one UV vertex.
DisjointSets ds(nc);
for (uint32_t c = 0; c < nc; ++c) {
if (!topo.border[c] && topo.twin[c] != kNoCorner) { // already connected
ds.unite(c, cornerNext(topo.twin[c]));
ds.unite(cornerNext(c), topo.twin[c]);
}
}
std::vector<uint32_t> welded; // edges to clear the seam of
for (uint32_t c : corners) {
const uint32_t d = topo.twin[c];
if (d == kNoCorner) continue;
const uint32_t n = cornerNext(c);
// The edge c -> next(c) has both ends selected, and so does its twin's side.
if (!inSet[n] || !inSet[d] || !inSet[cornerNext(d)]) continue;
ds.unite(c, cornerNext(d));
ds.unite(n, d);
welded.push_back(c);
}
// Only the selected corners' groups are averaged.
std::map<uint32_t, std::pair<glm::dvec2, uint32_t>> sums;
for (uint32_t c : corners) sums[ds.find(c)];
for (uint32_t c = 0; c < nc; ++c) {
auto it = sums.find(ds.find(c));
if (it == sums.end()) continue;
auto& s = it->second;
s.first += glm::dvec2(m.uvs[c]);
++s.second;
}
std::vector<uint32_t> verts;
for (uint32_t c = 0; c < nc; ++c) {
auto it = sums.find(ds.find(c));
if (it == sums.end()) continue;
m.uvs[c] = glm::vec2(it->second.first / double(it->second.second));
if (inSet[c]) verts.push_back(vert(c));
}
std::sort(verts.begin(), verts.end());
verts.erase(std::unique(verts.begin(), verts.end()), verts.end());
if (!welded.empty() && m.uvFlags.size() == nc) uvSetSeams(m, topo.twin, welded, false);
m.facesDirty = true;
return verts.size();
}
size_t uvSplit(Mesh& m, const UvTopology& topo, const UvSelection& sel) {
if (!sel.valid(m)) return 0;
std::vector<uint32_t> cut;
if (sel.mode == UvSelectMode::Edge) {
for (uint32_t c = 0; c < sel.corners.size(); ++c)
if (sel.corners[c] && topo.twin[c] != kNoCorner) cut.push_back(c);
} else if (sel.mode == UvSelectMode::Vertex) {
// Edges with both ends selected.
for (uint32_t c = 0; c < sel.corners.size(); ++c)
if (sel.corners[c] && sel.corners[cornerNext(c)] && topo.twin[c] != kNoCorner) cut.push_back(c);
} else {
cut = uvFaceSetBorder(m, topo.twin, sel.faces);
}
cut.erase(std::remove_if(cut.begin(), cut.end(), [&](uint32_t c) { return topo.border[c]; }), cut.end());
if (cut.empty()) return 0;
uvSetSeams(m, topo.twin, cut, true);
return cut.size();
}
size_t uvStraighten(Mesh& m, const UvTopology& topo, const std::vector<uint32_t>& corners) {
if (corners.size() < 2 || m.uvs.size() != m.triangleCount() * 3) return 0;
std::vector<uint8_t> seen(topo.uvVertexCount, 0);
std::vector<glm::vec2> pts;
for (uint32_t c : corners)
if (!seen[topo.uvVertex[c]]) {
seen[topo.uvVertex[c]] = 1;
pts.push_back(m.uvs[c]);
}
if (pts.size() < 2) return 0;
glm::dvec2 mean(0.0);
for (glm::vec2 p : pts) mean += glm::dvec2(p);
mean /= double(pts.size());
double sxx = 0, syy = 0;
for (glm::vec2 p : pts) {
const glm::dvec2 d = glm::dvec2(p) - mean;
sxx += d.x * d.x;
syy += d.y * d.y;
}
const bool horizontal = sxx >= syy;
for (uint32_t c : corners) {
if (horizontal) m.uvs[c].y = float(mean.y);
else m.uvs[c].x = float(mean.x);
}
m.facesDirty = true;
return pts.size();
}
void uvFlipIslands(Mesh& m, const UvTopology& topo, const std::vector<uint8_t>& islands, bool horizontal) {
std::vector<uint32_t> offsets, corners;
islandCorners(topo, offsets, corners);
for (uint32_t i = 0; i < topo.islandCount; ++i) {
if (!islands[i]) continue;
std::vector<uint32_t> cs(corners.begin() + offsets[i], corners.begin() + offsets[i + 1]);
const glm::vec2 c = uvCenter(m.uvs, cs);
uvTransform(m.uvs, cs, horizontal ? glm::mat2(-1, 0, 0, 1) : glm::mat2(1, 0, 0, -1), c, glm::vec2(0.0f));
}
m.facesDirty = true;
}
size_t uvSetDensity(Mesh& m, const UvTopology& topo, const std::vector<uint8_t>& islands, float density, int resolution) {
if (density <= 0.0f) return 0;
const std::vector<float> current = uvIslandDensity(m, topo, resolution);
std::vector<uint32_t> offsets, corners;
islandCorners(topo, offsets, corners);
size_t n = 0;
for (uint32_t i = 0; i < topo.islandCount; ++i) {
if (!islands[i] || current[i] <= 0.0f) continue;
std::vector<uint32_t> cs(corners.begin() + offsets[i], corners.begin() + offsets[i + 1]);
const float k = density / current[i];
uvTransform(m.uvs, cs, glm::mat2(k), uvCenter(m.uvs, cs), glm::vec2(0.0f));
++n;
}
m.facesDirty = true;
return n;
}
std::vector<TrimStrip> equalTrimStrips(int count) {
count = std::clamp(count, 1, 64);
std::vector<TrimStrip> out;
for (int i = 0; i < count; ++i) {
TrimStrip s;
// Strip 1 at the top of the texture (v = 1), as trim sheets are drawn.
s.v1 = 1.0f - float(i) / float(count);
s.v0 = 1.0f - float(i + 1) / float(count);
s.name = "Strip " + std::to_string(i + 1);
out.push_back(s);
}
return out;
}
bool parseTrimStrips(const std::string& text, std::vector<TrimStrip>& out, std::string& error) {
out.clear();
std::string s;
for (char ch : text)
if (!std::isspace(static_cast<unsigned char>(ch))) s += ch;
if (s.empty()) {
error = "No trim strips given";
return false;
}
try {
if (s.find_first_of(",;-") == std::string::npos) {
const int n = std::stoi(s);
if (n < 1 || n > 64) throw std::out_of_range("count");
out = equalTrimStrips(n);
return true;
}
if (s.find('-') != std::string::npos) { // v ranges "a-b;c-d"
std::stringstream ss(s);
std::string part;
while (std::getline(ss, part, ';')) {
const size_t dash = part.find('-', 1);
if (dash == std::string::npos) throw std::invalid_argument("range");
TrimStrip st;
st.v0 = std::stof(part.substr(0, dash));
st.v1 = std::stof(part.substr(dash + 1));
if (st.v1 < st.v0) std::swap(st.v0, st.v1);
if (st.v0 < 0.0f || st.v1 > 1.0f || st.v1 - st.v0 <= 0.0f) throw std::out_of_range("range");
st.name = "Strip " + std::to_string(out.size() + 1);
out.push_back(st);
}
} else { // heights from the top "0.5,0.25,0.25"
std::stringstream ss(s);
std::string part;
std::vector<float> h;
while (std::getline(ss, part, ',')) {
h.push_back(std::stof(part));
if (h.back() <= 0.0f) throw std::out_of_range("height");
}
float total = 0.0f;
for (float x : h) total += x;
float top = 1.0f;
for (float x : h) {
TrimStrip st;
st.v1 = top;
top -= x / total;
st.v0 = std::max(top, 0.0f);
st.name = "Strip " + std::to_string(out.size() + 1);
out.push_back(st);
}
}
} catch (...) {
error = "Trim strips: give a count (4), heights from the top (0.5,0.25,0.25) or v ranges (0-0.5;0.5-1)";
out.clear();
return false;
}
if (out.empty()) {
error = "No trim strips given";
return false;
}
return true;
}
size_t uvTrimIslands(Mesh& m, const UvTopology& topo, const std::vector<uint8_t>& islands, const TrimStrip& strip,
bool fitWidth, float margin) {
if (m.uvs.size() != m.triangleCount() * 3) return 0;
const float height = (strip.v1 - strip.v0) - 2.0f * margin;
if (height <= 0.0f) return 0;
std::vector<uint32_t> offsets, corners;
islandCorners(topo, offsets, corners);
std::vector<uint32_t> row; // every corner placed, for fitWidth
float cursor = 0.0f;
size_t n = 0;
for (uint32_t i = 0; i < topo.islandCount; ++i) {
if (!islands[i]) continue;
std::vector<uint32_t> cs(corners.begin() + offsets[i], corners.begin() + offsets[i + 1]);
std::vector<glm::vec2> pts;
pts.reserve(cs.size());
for (uint32_t c : cs) pts.push_back(m.uvs[c]);
// Lengthwise along u.
const float a = minAreaRectAngle(pts);
const float ca = std::cos(a), sa = std::sin(a);
glm::vec2 lo(std::numeric_limits<float>::max()), hi(std::numeric_limits<float>::lowest());
for (glm::vec2& p : pts) {
p = rotate(p, ca, sa);
lo = glm::min(lo, p);
hi = glm::max(hi, p);
}
const glm::vec2 size = hi - lo;
if (size.y <= 0.0f || size.x <= 0.0f) continue;
const float k = height / size.y;
for (size_t j = 0; j < cs.size(); ++j)
m.uvs[cs[j]] = glm::vec2(cursor + (pts[j].x - lo.x) * k, strip.v0 + margin + (pts[j].y - lo.y) * k);
cursor += size.x * k + margin;
row.insert(row.end(), cs.begin(), cs.end());
++n;
}
const float width = cursor - margin;
if (fitWidth && width > 0.0f)
for (uint32_t c : row) m.uvs[c].x /= width;
m.facesDirty = true;
return n;
}
} // namespace sf