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
//
// QRemesh: field-aligned quad remeshing (see QRemesh.h for the outline). The field formulas (extrinsic 4-RoSy
// orientation and position compatibility, the middle point of two tangent planes) follow Instant Meshes
// (Jakob et al. 2015); hierarchy, extraction, quad splitting and relaxation are our own. Instant Meshes is
// Copyright (c) 2015 Wenzel Jakob, Daniele Panozzo, Marco Tarini, and Olga Sorkine-Hornung, BSD-3-Clause; see
// THIRD_PARTY_NOTICES.md.
#include "core/QRemesh.h"
#include "core/Parallel.h"
#include "core/QRemeshInternal.h"
#include "core/SurfaceQuery.h"
#include <algorithm>
#include <chrono>
#include <map>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <functional>
#include <limits>
#include <numeric>
#include <unordered_map>
namespace sf {
namespace {
using glm::ivec2;
using glm::vec3;
constexpr uint32_t kNone = ~0u;
uint64_t edgeKey(uint32_t a, uint32_t b) { return a < b ? (uint64_t(a) << 32) | b : (uint64_t(b) << 32) | a; }
vec3 safeNormalize(const vec3& v, const vec3& fallback = vec3(0, 0, 1)) {
const float l = glm::length(v);
return l > 1e-20f ? v / l : fallback;
}
// Any unit vector perpendicular to n.
vec3 anyTangent(const vec3& n) {
const vec3 a = std::abs(n.x) < 0.6f ? vec3(1, 0, 0) : vec3(0, 1, 0);
return safeNormalize(glm::cross(n, a));
}
struct Rng {
uint64_t s;
explicit Rng(uint64_t seed) : s(seed * 0x9E3779B97F4A7C15ull + 0x632BE59BD9B4E019ull) {}
float next() { // 0..1
s ^= s << 13;
s ^= s >> 7;
s ^= s << 17;
return float((s >> 40) & 0xFFFFFF) / float(0x1000000);
}
};
// --- Instant Meshes field formulas (4-RoSy, 4-PoSy, extrinsic) -------------------------------------------
// The pair of representatives of q0's and q1's crosses (each a direction and its 90 degree rotations) that
// are closest to each other.
inline std::pair<vec3, vec3> compatOrientation(const vec3& q0, const vec3& n0, const vec3& q1, const vec3& n1) {
const vec3 A[2] = {q0, glm::cross(n0, q0)};
const vec3 B[2] = {q1, glm::cross(n1, q1)};
float best = -1.0f;
int ba = 0, bb = 0;
for (int a = 0; a < 2; ++a)
for (int b = 0; b < 2; ++b) {
const float s = std::abs(glm::dot(A[a], B[b]));
if (s > best) best = s, ba = a, bb = b;
}
const float dp = glm::dot(A[ba], B[bb]);
return {A[ba], B[bb] * (dp < 0.0f ? -1.0f : 1.0f)};
}
// q1's cross member that best matches q0 (q1 rotated into q0's frame).
inline vec3 alignTo(const vec3& q0, const vec3& n0, const vec3& q1, const vec3& n1) {
const vec3 t1 = glm::cross(n1, q1);
const vec3 cands[4] = {q1, t1, -q1, -t1};
int best = 0;
float bd = -2.0f;
for (int k = 0; k < 4; ++k)
if (const float d = glm::dot(q0, cands[k]); d > bd) bd = d, best = k;
return cands[best];
}
// The point minimising the distance to p0 and p1 while lying on both tangent planes (Instant Meshes).
inline vec3 middlePoint(const vec3& p0, const vec3& n0, const vec3& p1, const vec3& n1) {
const float n0p0 = glm::dot(n0, p0), n0p1 = glm::dot(n0, p1), n1p0 = glm::dot(n1, p0), n1p1 = glm::dot(n1, p1);
const float n0n1 = glm::dot(n0, n1), denom = 1.0f / (1.0f - n0n1 * n0n1 + 1e-4f);
const float l0 = 2.0f * (n0p1 - n0p0 - n0n1 * (n1p0 - n1p1)) * denom;
const float l1 = 2.0f * (n1p0 - n1p1 - n0n1 * (n0p1 - n0p0)) * denom;
return 0.5f * (p0 + p1) - 0.25f * (n0 * l0 + n1 * l1);
}
inline ivec2 floorIndex(const vec3& o, const vec3& q, const vec3& t, float inv, const vec3& p) {
const vec3 d = p - o;
return {int(std::floor(glm::dot(q, d) * inv)), int(std::floor(glm::dot(t, d) * inv))};
}
inline vec3 latticePoint(const vec3& o, const vec3& q, const vec3& t, float s, ivec2 i) {
return o + q * (float(i.x) * s) + t * (float(i.y) * s);
}
// The lattice corners of vertex 0 and vertex 1 (q1 already aligned with q0) nearest each other around the
// middle of the two vertices, as lattice indices relative to o0 / o1, and their squared distance.
inline float compatIndex(const vec3& v0, const vec3& n0, const vec3& q0, const vec3& o0, float s0, const vec3& v1,
const vec3& n1, const vec3& q1, const vec3& o1, float s1, ivec2& i0, ivec2& i1) {
const vec3 t0 = glm::cross(n0, q0), t1 = glm::cross(n1, q1);
const vec3 mid = middlePoint(v0, n0, v1, n1);
const ivec2 b0 = floorIndex(o0, q0, t0, 1.0f / s0, mid), b1 = floorIndex(o1, q1, t1, 1.0f / s1, mid);
vec3 p1[4];
for (int b = 0; b < 4; ++b) p1[b] = latticePoint(o1, q1, t1, s1, b1 + ivec2(b & 1, b >> 1));
float best = std::numeric_limits<float>::max();
for (int a = 0; a < 4; ++a) {
const ivec2 c0 = b0 + ivec2(a & 1, a >> 1);
const vec3 p0 = latticePoint(o0, q0, t0, s0, c0);
for (int b = 0; b < 4; ++b) {
const vec3 d = p0 - p1[b];
const float cost = glm::dot(d, d);
if (cost < best) best = cost, i0 = c0, i1 = b1 + ivec2(b & 1, b >> 1);
}
}
return best;
}
inline vec3 positionRound(const vec3& o, const vec3& q, const vec3& n, const vec3& p, float s) {
const vec3 t = glm::cross(n, q), d = p - o;
const float inv = 1.0f / s;
return o + q * (std::round(glm::dot(q, d) * inv) * s) + t * (std::round(glm::dot(t, d) * inv) * s);
}
// --- Working surface ------------------------------------------------------------------------------------
using qr::WorkMesh;
// Keeps the side of the plane (axis coordinate >= 0), splitting the triangles that cross it.
WorkMesh cutAtPlane(const WorkMesh& in, int axis, float eps) {
WorkMesh out;
std::vector<vec3> P = in.P;
for (vec3& p : P)
if (std::abs(p[axis]) <= eps) p[axis] = 0.0f;
std::vector<uint32_t> remap(P.size(), kNone);
auto keep = [&](uint32_t v) {
if (remap[v] == kNone) {
remap[v] = uint32_t(out.P.size());
out.P.push_back(P[v]);
if (!in.color.empty()) out.color.push_back(in.color[v]);
}
return remap[v];
};
std::unordered_map<uint64_t, uint32_t> cuts;
auto cutPoint = [&](uint32_t a, uint32_t b) {
auto [it, inserted] = cuts.try_emplace(edgeKey(a, b), 0);
if (inserted) {
const float t = P[a][axis] / (P[a][axis] - P[b][axis]);
vec3 p = glm::mix(P[a], P[b], t);
p[axis] = 0.0f;
it->second = uint32_t(out.P.size());
out.P.push_back(p);
if (!in.color.empty()) out.color.push_back(glm::mix(in.color[a], in.color[b], t));
}
return it->second;
};
for (size_t t = 0; t < in.T.size(); ++t) {
const glm::uvec3 tri = in.T[t];
int side[3];
bool anyPos = false, anyNeg = false;
for (int k = 0; k < 3; ++k) {
const float x = P[tri[k]][axis];
side[k] = x > 0.0f ? 1 : x < 0.0f ? -1 : 0;
anyPos |= side[k] > 0;
anyNeg |= side[k] < 0;
}
if (!anyPos) continue;
uint32_t poly[4];
int n = 0;
if (!anyNeg) {
for (int k = 0; k < 3; ++k) poly[n++] = keep(tri[k]);
} else {
for (int k = 0; k < 3; ++k) {
const uint32_t a = tri[k], b = tri[(k + 1) % 3];
if (side[k] >= 0) poly[n++] = keep(a);
if ((side[k] > 0 && side[(k + 1) % 3] < 0) || (side[k] < 0 && side[(k + 1) % 3] > 0)) poly[n++] = cutPoint(a, b);
}
}
for (int k = 1; k + 1 < n; ++k) {
out.T.push_back({poly[0], poly[k], poly[k + 1]});
out.group.push_back(in.group[t]);
}
}
return out;
}
// Splits edges longer than `maxEdge` at their midpoints (each triangle into 2, 3 or 4, conforming), pass after
// pass, so coarse parts of the input (a low-poly base under a dense sculpt) are dense enough for the fields.
// Stops early when the triangle count would pass `maxTriangles`.
WorkMesh refineLongEdges(WorkMesh m, float maxEdge, size_t maxTriangles) {
const float max2 = maxEdge * maxEdge;
for (int pass = 0; pass < 12; ++pass) {
std::unordered_map<uint64_t, uint32_t> mids;
auto longEdge = [&](uint32_t a, uint32_t b) { return glm::dot(m.P[a] - m.P[b], m.P[a] - m.P[b]) > max2; };
size_t extra = 0;
for (const glm::uvec3& t : m.T)
for (int k = 0; k < 3; ++k)
if (longEdge(t[k], t[(k + 1) % 3])) ++extra;
if (extra == 0 || m.T.size() + extra > maxTriangles) break;
auto mid = [&](uint32_t a, uint32_t b) {
auto [it, inserted] = mids.try_emplace(edgeKey(a, b), uint32_t(m.P.size()));
if (inserted) {
m.P.push_back(0.5f * (m.P[a] + m.P[b]));
if (!m.color.empty()) m.color.push_back(0.5f * (m.color[a] + m.color[b]));
}
return it->second;
};
std::vector<glm::uvec3> T;
std::vector<uint32_t> G;
T.reserve(m.T.size() + extra);
G.reserve(m.T.size() + extra);
for (size_t i = 0; i < m.T.size(); ++i) {
const glm::uvec3 t = m.T[i];
const uint32_t g = m.group[i];
uint32_t mk[3];
int marked = 0, first = -1;
for (int k = 0; k < 3; ++k) {
mk[k] = longEdge(t[k], t[(k + 1) % 3]) ? mid(t[k], t[(k + 1) % 3]) : kNone;
if (mk[k] != kNone) {
++marked;
if (first < 0) first = k;
}
}
auto emit = [&](uint32_t a, uint32_t b, uint32_t c) {
T.push_back({a, b, c});
G.push_back(g);
};
if (marked == 0) {
emit(t.x, t.y, t.z);
} else if (marked == 3) {
emit(t.x, mk[0], mk[2]);
emit(mk[0], t.y, mk[1]);
emit(mk[2], mk[1], t.z);
emit(mk[0], mk[1], mk[2]);
} else if (marked == 1) {
const int k = first;
const uint32_t a = t[k], b = t[(k + 1) % 3], c = t[(k + 2) % 3], ab = mk[k];
emit(a, ab, c);
emit(ab, b, c);
} else { // two edges: the unmarked one is (c, a) after rotating so edges k and k+1 are marked
int k = 0;
while (!(mk[k] != kNone && mk[(k + 1) % 3] != kNone)) ++k;
const uint32_t a = t[k], b = t[(k + 1) % 3], c = t[(k + 2) % 3], ab = mk[k], bc = mk[(k + 1) % 3];
emit(ab, b, bc);
emit(a, ab, bc);
emit(a, bc, c);
}
}
m.T.swap(T);
m.group.swap(G);
}
return m;
}
// --- Hierarchy ------------------------------------------------------------------------------------------
enum : uint8_t { kFree = 0, kLine = 1, kPoint = 2 };
struct Level {
std::vector<vec3> V, N;
std::vector<float> A;
std::vector<uint32_t> off, adj; // CSR adjacency
std::vector<float> w;
std::vector<uint32_t> up; // index of the merged vertex in the next (coarser) level
// Constraints: kLine = the lattice has a line through cpos along cdir; kPoint = a lattice corner at cpos.
std::vector<uint8_t> ctype;
std::vector<vec3> cdir, cpos;
std::vector<uint8_t> boundary; // on an open edge of the mesh
std::vector<vec3> color; // vertex paint (useVertex paint only)
// QRemesh Guides: how strongly (0..1) the orientation turns to the nearest curve's direction gdir (empty
// without guides).
std::vector<float> gw;
std::vector<vec3> gdir;
// Line constraints on a closed guide (empty without closed guides): which (-1: none), where along it, and
// whether cpos is pinned as a lattice corner (pinClosedGuides).
std::vector<int32_t> gid;
std::vector<float> garc;
std::vector<uint8_t> cfix;
// Fields.
std::vector<vec3> Q, O;
std::vector<float> S;
std::vector<std::vector<uint32_t>> phases; // independent sets for parallel Gauss-Seidel
float meanEdge = 0.0f;
size_t size() const { return V.size(); }
};
void computePhases(Level& l) {
l.phases.clear();
const size_t n = l.size();
if (n < 4000) { // sequential sweeps: one phase in index order
l.phases.emplace_back(n);
std::iota(l.phases[0].begin(), l.phases[0].end(), 0u);
return;
}
std::vector<uint8_t> color(n, 255);
std::vector<uint8_t> used;
for (uint32_t i = 0; i < n; ++i) {
used.assign(64, 0);
for (uint32_t k = l.off[i]; k < l.off[i + 1]; ++k)
if (color[l.adj[k]] < 64) used[color[l.adj[k]]] = 1;
uint8_t c = 0;
while (c < 63 && used[c]) ++c;
color[i] = c;
if (c >= l.phases.size()) l.phases.resize(c + 1);
l.phases[c].push_back(i);
}
}
void computeMeanEdge(Level& l) {
double sum = 0.0;
size_t cnt = 0;
for (uint32_t i = 0; i < l.size(); ++i)
for (uint32_t k = l.off[i]; k < l.off[i + 1]; ++k) {
sum += glm::length(l.V[i] - l.V[l.adj[k]]);
++cnt;
}
l.meanEdge = cnt ? float(sum / double(cnt)) : 0.0f;
}
// Level 0 from the working mesh: vertex graph, area-weighted normals, constraints on open edges and (with
// keepGroups) face group borders.
Level buildFinest(const WorkMesh& m, bool keepGroups, float sharpCos, std::vector<std::pair<vec3, vec3>>& boundarySegs,
std::vector<uint8_t>& boundarySegIsCut, std::vector<std::pair<vec3, vec3>>& borderSegs, int symAxis) {
Level l;
const size_t nv = m.P.size();
l.V = m.P;
l.N.assign(nv, vec3(0.0f));
l.A.assign(nv, 0.0f);
for (const glm::uvec3& t : m.T) {
const vec3 n = glm::cross(m.P[t.y] - m.P[t.x], m.P[t.z] - m.P[t.x]);
const float a = 0.5f * glm::length(n);
for (int k = 0; k < 3; ++k) {
l.N[t[k]] += n;
l.A[t[k]] += a / 3.0f;
}
}
for (auto& n : l.N) n = safeNormalize(n);
// Edges with the triangles on each side.
struct EdgeInfo {
uint32_t a, b;
uint32_t t0, t1;
int count;
};
// Each edge found from its lower vertex: the triangles around a vertex, their edges to higher vertices.
std::vector<uint32_t> vtOff(nv + 1, 0), vt(m.T.size() * 3);
for (const glm::uvec3& t : m.T)
for (int k = 0; k < 3; ++k) ++vtOff[t[k] + 1];
for (size_t i = 0; i < nv; ++i) vtOff[i + 1] += vtOff[i];
{
std::vector<uint32_t> fill(vtOff.begin(), vtOff.end() - 1);
for (uint32_t t = 0; t < m.T.size(); ++t)
for (int k = 0; k < 3; ++k) vt[fill[m.T[t][k]]++] = t;
}
std::vector<uint32_t> edgeOff(nv + 1, 0);
std::vector<EdgeInfo> edges;
auto vertexEdges = [&](uint32_t a, auto&& emit) {
std::pair<uint32_t, uint32_t> local[64]; // (other vertex, triangle)
std::vector<std::pair<uint32_t, uint32_t>> big;
size_t n = 0;
auto push = [&](uint32_t b, uint32_t t) {
if (n < 64) local[n++] = {b, t};
else {
if (big.empty()) big.assign(local, local + 64);
big.push_back({b, t});
++n;
}
};
for (uint32_t k = vtOff[a]; k < vtOff[a + 1]; ++k) {
const uint32_t t = vt[k];
for (int e = 0; e < 3; ++e) {
const uint32_t x = m.T[t][e], y = m.T[t][(e + 1) % 3];
if (x == y) continue;
if (x == a && y > a) push(y, t);
else if (y == a && x > a) push(x, t);
}
}
std::pair<uint32_t, uint32_t>* p = big.empty() ? local : big.data();
std::sort(p, p + n);
for (size_t i = 0; i < n;) {
size_t j = i;
while (j < n && p[j].first == p[i].first) ++j;
emit(EdgeInfo{a, p[i].first, p[i].second, j - i > 1 ? p[i + 1].second : kNone, int(j - i)});
i = j;
}
};
parallelFor(nv, [&](size_t b0, size_t e0) {
for (size_t a = b0; a < e0; ++a) {
uint32_t count = 0;
vertexEdges(uint32_t(a), [&](const EdgeInfo&) { ++count; });
edgeOff[a + 1] = count;
}
});
for (size_t i = 0; i < nv; ++i) edgeOff[i + 1] += edgeOff[i];
edges.resize(edgeOff[nv]);
parallelFor(nv, [&](size_t b0, size_t e0) {
for (size_t a = b0; a < e0; ++a) {
uint32_t at = edgeOff[a];
vertexEdges(uint32_t(a), [&](const EdgeInfo& e) { edges[at++] = e; });
}
});
// CSR adjacency.
l.off.assign(nv + 1, 0);
for (const EdgeInfo& e : edges) ++l.off[e.a + 1], ++l.off[e.b + 1];
for (size_t i = 0; i < nv; ++i) l.off[i + 1] += l.off[i];
l.adj.resize(l.off[nv]);
l.w.assign(l.off[nv], 1.0f);
{
std::vector<uint32_t> fill(l.off.begin(), l.off.end() - 1);
for (const EdgeInfo& e : edges) {
l.adj[fill[e.a]++] = e.b;
l.adj[fill[e.b]++] = e.a;
}
}
// Feature edges: open edges and face group borders.
l.ctype.assign(nv, kFree);
l.cdir.assign(nv, vec3(0.0f));
l.cpos = l.V;
l.boundary.assign(nv, 0);
std::vector<std::vector<uint32_t>> featureNb(nv);
for (const EdgeInfo& e : edges) {
const bool open = e.count == 1;
bool border = keepGroups && e.count == 2 && m.group[e.t0] != m.group[e.t1];
if (!border && sharpCos < 1.0f && e.count == 2) { // a hard edge (Keep Hard Edges)
const glm::uvec3 a = m.T[e.t0], b = m.T[e.t1];
const vec3 na = safeNormalize(glm::cross(m.P[a.y] - m.P[a.x], m.P[a.z] - m.P[a.x]));
const vec3 nb = safeNormalize(glm::cross(m.P[b.y] - m.P[b.x], m.P[b.z] - m.P[b.x]));
border = glm::dot(na, nb) < sharpCos;
}
if (!open && !border) continue;
featureNb[e.a].push_back(e.b);
featureNb[e.b].push_back(e.a);
if (open) {
l.boundary[e.a] = l.boundary[e.b] = 1;
boundarySegs.push_back({m.P[e.a], m.P[e.b]});
boundarySegIsCut.push_back(symAxis >= 0 && m.P[e.a][symAxis] == 0.0f && m.P[e.b][symAxis] == 0.0f);
} else {
borderSegs.push_back({m.P[e.a], m.P[e.b]});
}
}
// Tangent of the feature curve at each vertex, smoothed along the curve (borders on triangle meshes zigzag).
std::vector<vec3> dir(nv, vec3(0.0f));
for (uint32_t v = 0; v < nv; ++v) {
const auto& f = featureNb[v];
if (f.size() == 2) dir[v] = safeNormalize(m.P[f[0]] - m.P[f[1]], vec3(0.0f));
}
for (int it = 0; it < 4; ++it) {
std::vector<vec3> next = dir;
for (uint32_t v = 0; v < nv; ++v) {
if (featureNb[v].size() != 2) continue;
vec3 sum = dir[v];
for (uint32_t u : featureNb[v])
if (featureNb[u].size() == 2) sum += glm::dot(dir[u], sum) < 0.0f ? -dir[u] : dir[u];
next[v] = safeNormalize(sum, dir[v]);
}
dir.swap(next);
}
for (uint32_t v = 0; v < nv; ++v) {
const size_t k = featureNb[v].size();
if (k == 0) continue;
if (k == 2) {
const vec3 d = dir[v] - l.N[v] * glm::dot(l.N[v], dir[v]);
if (glm::length(d) > 1e-6f) {
l.ctype[v] = kLine;
l.cdir[v] = glm::normalize(d);
continue;
}
}
l.ctype[v] = kPoint; // junction of several borders, or the end of one
}
if (!m.color.empty()) l.color = m.color;
computeMeanEdge(l);
return l;
}
// --- QRemesh Guides --------------------------------------------------------------------------------------
// A closed guide (or, with symmetry, a curve from the seam to the seam: half of a loop across the middle): its
// points (in order), the arc length at each, and how many lattice steps go round (or along) it.
struct ClosedGuide {
std::vector<vec3> points;
std::vector<float> arc; // arc[i]: length from points[0] to points[i]
float length = 0.0f;
SegmentBVH bvh;
float steps = 0.0f; // set by closedGuideSize
bool loop = true; // false: from the seam to the seam, both ends lattice corners
size_t lines = 0; // finest-level vertices with a line constraint on it (none: not on this piece)
vec3 at(float s) const { // the point at arc length s (wrapping round a loop)
if (!loop) {
s = std::clamp(s, 0.0f, length);
if (s >= length) return points.back();
}
s = std::fmod(s, length);
if (s < 0.0f) s += length;
const size_t i = size_t(std::upper_bound(arc.begin(), arc.end(), s) - arc.begin()) - 1;
const size_t j = (i + 1) % points.size();
const float len = (j ? arc[j] : length) - arc[i];
return glm::mix(points[i], points[j], len > 0.0f ? (s - arc[i]) / len : 0.0f);
}
};
// QRemesh Guides on the finest level: vertices on a curve (within about half an edge of it) get a line
// constraint along it, so the lattice puts a line, and the result an edge loop, there; vertices within `radius`
// turn their orientation towards the curve's direction with a weight falling off from 1 on the curve. Vertices
// with a constraint already (open edges, borders, hard edges) keep theirs. The curves' segments are added to
// `guideSegs`, so relaxation keeps the loop's vertices on the curve. Line vertices on a closed guide remember
// which (Level::gid) and where along it (Level::garc), for pinClosedGuides; so do those on a curve with both
// ends on the symmetry plane (`axis`; the half of a loop across the middle, cut there by qremesh).
void applyGuides(Level& l, const std::vector<QRemeshGuide>& guides, float radius, int axis,
std::vector<std::pair<vec3, vec3>>& guideSegs, std::vector<ClosedGuide>& closed) {
std::vector<vec3> a, b, ta, tb; // segments and the curve's tangent at each end
std::vector<int32_t> segClosed; // per segment: its closed guide, or -1
std::vector<float> segArc; // arc length at the segment's start (closed guides)
closed.clear();
for (const QRemeshGuide& g : guides) {
const size_t n = g.points.size();
if (n < 2) continue;
auto tangent = [&](size_t i) {
const size_t prev = i > 0 ? i - 1 : g.closed ? n - 1 : 0, next = i + 1 < n ? i + 1 : g.closed ? 0 : n - 1;
return safeNormalize(g.points[next] - g.points[prev], vec3(0.0f));
};
const bool loop = g.closed && n > 2;
const bool seamToSeam = !g.closed && axis >= 0 && g.points.front()[axis] == 0.0f && g.points.back()[axis] == 0.0f;
const bool pinned = loop || seamToSeam;
ClosedGuide c;
c.loop = loop;
const size_t segs = loop ? n : n - 1;
for (size_t i = 0; i < segs; ++i) {
const size_t j = (i + 1) % n;
a.push_back(g.points[i]);
b.push_back(g.points[j]);
ta.push_back(tangent(i));
tb.push_back(tangent(j));
guideSegs.push_back({g.points[i], g.points[j]});
segClosed.push_back(pinned ? int32_t(closed.size()) : -1);
segArc.push_back(c.length);
if (pinned) {
c.points.push_back(g.points[i]);
c.arc.push_back(c.length);
c.length += glm::length(g.points[j] - g.points[i]);
}
}
if (seamToSeam) c.points.push_back(g.points.back()), c.arc.push_back(c.length);
if (pinned) {
c.bvh.build(std::vector<vec3>(a.end() - long(segs), a.end()), std::vector<vec3>(b.end() - long(segs), b.end()));
closed.push_back(std::move(c));
}
}
if (a.empty()) return;
SegmentBVH bvh;
bvh.build(a, b);
const size_t nv = l.size();
// Where a curve from the seam to the seam meets it: a lattice corner (the seam vertex nearest each end), so
// the loop crosses the middle there (relaxation pins a quad vertex to it, as at the source's corners).
for (const ClosedGuide& c : closed) {
if (c.loop) continue;
for (const vec3& end : {c.points.front(), c.points.back()}) {
uint32_t best = kNone;
float bestD = radius * radius;
for (uint32_t v = 0; v < nv; ++v) {
const float d = glm::dot(l.V[v] - end, l.V[v] - end);
if (l.boundary[v] && d < bestD) bestD = d, best = v;
}
if (best == kNone) continue;
l.ctype[best] = kPoint;
l.cpos[best] = end;
}
}
l.gw.assign(nv, 0.0f);
l.gdir.assign(nv, vec3(0.0f));
if (!closed.empty()) {
l.gid.assign(nv, -1);
l.garc.assign(nv, 0.0f);
}
parallelFor(nv, [&](size_t b0, size_t e0) {
for (size_t v = b0; v < e0; ++v) {
SurfaceHit hit;
if (!bvh.closestPoint(l.V[v], radius, hit)) continue;
vec3 t = ta[hit.prim] * hit.bary.x + tb[hit.prim] * hit.bary.y;
if (glm::dot(t, ta[hit.prim]) < 0.0f) t = ta[hit.prim];
const vec3 n = l.N[v];
t -= n * glm::dot(n, t);
if (glm::length(t) < 1e-6f) continue;
t = glm::normalize(t);
const float f = 1.0f - hit.distance / radius;
l.gw[v] = f * f;
l.gdir[v] = t;
if (l.ctype[v] != kFree) continue;
float edge = 0.0f;
for (uint32_t k = l.off[v]; k < l.off[v + 1]; ++k) edge += glm::length(l.V[l.adj[k]] - l.V[v]);
const uint32_t deg = l.off[v + 1] - l.off[v];
if (deg && hit.distance < 0.6f * edge / float(deg)) {
l.ctype[v] = kLine;
l.cdir[v] = t;
l.cpos[v] = hit.position;
if (const int32_t c = segClosed[hit.prim]; c >= 0) {
l.gid[v] = c;
l.garc[v] = segArc[hit.prim] + hit.bary.y * glm::length(b[hit.prim] - a[hit.prim]);
}
}
}
});
for (int32_t c : l.gid)
if (c >= 0) ++closed[size_t(c)].lines;
}
// A loop's lattice closes up only when its length is a whole number of lattice steps; otherwise the position
// field slips somewhere along it (a kink in the edge loop). Picks that number for each closed guide from the
// mean size on it, and scales the size field to fit, blended out over `reach`.
void closedGuideSize(const Level& L, std::vector<float>& S, std::vector<ClosedGuide>& closed, float reach) {
for (ClosedGuide& c : closed) {
double sum = 0.0;
size_t cnt = 0;
std::vector<std::pair<uint32_t, float>> near; // (vertex, distance)
for (uint32_t v = 0; v < L.size(); ++v) {
SurfaceHit hit;
if (!c.bvh.closestPoint(L.V[v], reach, hit)) continue;
near.push_back({v, hit.distance});
if (hit.distance < 0.25f * reach) sum += S[v], ++cnt;
}
c.steps = 0.0f;
if (!cnt) continue;
const float s = float(sum / double(cnt));
// An even number round a loop: a disk of quads has an even number of sides, so with an odd number the
// lattice inside needs an odd face, and it ends up on the loop (a gap in it). Along a curve from the
// seam to the seam any whole number does: its mirror image doubles it.
c.steps = c.loop ? std::max(4.0f, 2.0f * std::round(0.5f * c.length / s)) : std::max(1.0f, std::round(c.length / s));
const float f = c.length / (c.steps * s);
for (auto [v, d] : near) {
const float w = d < 0.25f * reach ? 1.0f : 1.0f - (d - 0.25f * reach) / (0.75f * reach);
S[v] *= 1.0f + (f - 1.0f) * w;
}
}
}
// Puts lattice corners at `steps` even places round each closed guide: every line vertex on it is pinned to the
// one nearest along the curve, so the corners round the loop agree with each other and it closes up cleanly.
void pinClosedGuides(Level& l, const std::vector<ClosedGuide>& closed) {
if (l.gid.empty()) return;
l.cfix.assign(l.size(), 0);
for (uint32_t v = 0; v < l.size(); ++v) {
if (l.gid[v] < 0 || l.ctype[v] != kLine) continue;
const ClosedGuide& c = closed[size_t(l.gid[v])];
if (c.steps <= 0.0f) continue;
const float step = c.length / c.steps;
l.cpos[v] = c.at(std::round(l.garc[v] / step) * step);
l.cfix[v] = 1;
}
}
// The next coarser level: greedy matching of neighbours with similar normals (Instant Meshes' ordering).
bool downsample(Level& f, Level& c) {
const size_t n = f.size();
struct Entry {
uint32_t i, j;
float order;
};
std::vector<Entry> entries;
entries.reserve(f.adj.size() / 2);
for (uint32_t i = 0; i < n; ++i)
for (uint32_t k = f.off[i]; k < f.off[i + 1]; ++k) {
const uint32_t j = f.adj[k];
if (j <= i) continue;
const float ratio = f.A[i] > f.A[j] ? f.A[i] / std::max(f.A[j], 1e-30f) : f.A[j] / std::max(f.A[i], 1e-30f);
entries.push_back({i, j, glm::dot(f.N[i], f.N[j]) * ratio});
}
std::sort(entries.begin(), entries.end(), [](const Entry& a, const Entry& b) { return a.order > b.order; });
std::vector<uint32_t>& up = f.up;
up.assign(n, kNone);
const bool colors = !f.color.empty();
const bool guided = !f.gw.empty();
auto addVertex = [&](uint32_t i) {
up[i] = uint32_t(c.V.size());
c.V.push_back(f.V[i]);
c.N.push_back(f.N[i]);
c.A.push_back(f.A[i]);
c.ctype.push_back(f.ctype[i]);
c.cdir.push_back(f.cdir[i]);
c.cpos.push_back(f.cpos[i]);
c.boundary.push_back(f.boundary[i]);
if (colors) c.color.push_back(f.color[i]);
if (guided) c.gw.push_back(f.gw[i]), c.gdir.push_back(f.gdir[i]);
if (!f.gid.empty()) c.gid.push_back(f.gid[i]), c.garc.push_back(f.garc[i]);
};
for (const Entry& e : entries) {
if (up[e.i] != kNone || up[e.j] != kNone) continue;
addVertex(e.i);
up[e.j] = up[e.i];
const uint32_t v = up[e.i];
const float ai = f.A[e.i], aj = f.A[e.j], a = std::max(ai + aj, 1e-30f);
c.V[v] = (f.V[e.i] * ai + f.V[e.j] * aj) / a;
c.N[v] = safeNormalize(f.N[e.i] * ai + f.N[e.j] * aj, f.N[e.i]);
c.A[v] = ai + aj;
if (colors) c.color[v] = (f.color[e.i] * ai + f.color[e.j] * aj) / a;
// Constraints: a point beats a line; otherwise keep the first child's.
if (f.ctype[e.j] > f.ctype[e.i]) {
c.ctype[v] = f.ctype[e.j];
c.cdir[v] = f.cdir[e.j];
c.cpos[v] = f.cpos[e.j];
if (!f.gid.empty()) c.gid[v] = f.gid[e.j], c.garc[v] = f.garc[e.j];
}
c.boundary[v] |= f.boundary[e.j];
if (guided && f.gw[e.j] > c.gw[v]) c.gw[v] = f.gw[e.j], c.gdir[v] = f.gdir[e.j]; // the stronger pull
}
for (uint32_t i = 0; i < n; ++i)
if (up[i] == kNone) addVertex(i);
const size_t nc = c.V.size();
if (nc >= n) return false;
// Coarse adjacency: the children's neighbours' parents, weights summed (per coarse vertex, in parallel).
std::vector<uint32_t> chOff(nc + 1, 0), ch(n);
for (uint32_t i = 0; i < n; ++i) ++chOff[up[i] + 1];
for (size_t v = 0; v < nc; ++v) chOff[v + 1] += chOff[v];
{
std::vector<uint32_t> fill(chOff.begin(), chOff.end() - 1);
for (uint32_t i = 0; i < n; ++i) ch[fill[up[i]]++] = i;
}
auto gather = [&](uint32_t v, std::vector<std::pair<uint32_t, float>>& l) {
l.clear();
for (uint32_t k = chOff[v]; k < chOff[v + 1]; ++k) {
const uint32_t i = ch[k];
for (uint32_t a = f.off[i]; a < f.off[i + 1]; ++a)
if (const uint32_t b = up[f.adj[a]]; b != v) l.push_back({b, f.w[a]});
}
std::sort(l.begin(), l.end(), [](auto& x, auto& y) { return x.first < y.first; });
size_t w = 0;
for (size_t k = 0; k < l.size(); ++k) {
if (w > 0 && l[w - 1].first == l[k].first) l[w - 1].second += l[k].second;
else l[w++] = l[k];
}
l.resize(w);
};
c.off.assign(nc + 1, 0);
parallelFor(nc, [&](size_t b0, size_t e0) {
std::vector<std::pair<uint32_t, float>> l;
for (size_t v = b0; v < e0; ++v) {
gather(uint32_t(v), l);
c.off[v + 1] = uint32_t(l.size());
}
});
for (size_t v = 0; v < nc; ++v) c.off[v + 1] += c.off[v];
c.adj.resize(c.off[nc]);
c.w.resize(c.off[nc]);
parallelFor(nc, [&](size_t b0, size_t e0) {
std::vector<std::pair<uint32_t, float>> l;
for (size_t v = b0; v < e0; ++v) {
gather(uint32_t(v), l);
for (size_t k = 0; k < l.size(); ++k) {
c.adj[c.off[v] + k] = l[k].first;
c.w[c.off[v] + k] = l[k].second;
}
}
});
computeMeanEdge(c);
return true;
}
// --- Field solvers --------------------------------------------------------------------------------------
void applyOrientationConstraint(const Level& l, uint32_t i, vec3& q) {
if (l.ctype[i] != kLine) return;
q = alignTo(q, l.N[i], l.cdir[i], l.N[i]);
}
void smoothOrientations(Level& l, int iterations) {
const auto& phases = l.phases;
for (int it = 0; it < iterations; ++it)
for (const auto& phase : phases)
parallelFor(phase.size(), [&](size_t b, size_t e) {
for (size_t k = b; k < e; ++k) {
const uint32_t i = phase[k];
const vec3 n = l.N[i];
vec3 sum = l.Q[i];
float wsum = 0.0f;
for (uint32_t a = l.off[i]; a < l.off[i + 1]; ++a) {
const uint32_t j = l.adj[a];
const float w = l.w[a];
const auto [x, y] = compatOrientation(sum, n, l.Q[j], l.N[j]);
sum = x * wsum + y * w;
sum -= n * glm::dot(n, sum);
wsum += w;
const float len = glm::length(sum);
if (len > 1e-20f) sum /= len;
}
if (glm::length(sum) < 0.5f) sum = l.Q[i];
if (!l.gw.empty() && l.gw[i] > 0.0f) { // turn towards the guide's direction
const vec3 g = l.gdir[i] - n * glm::dot(n, l.gdir[i]);
if (glm::length(g) > 1e-6f) {
const vec3 a = alignTo(sum, n, glm::normalize(g), n);
const vec3 m = glm::mix(sum, a, l.gw[i]);
sum = safeNormalize(m - n * glm::dot(n, m), sum);
}
}
applyOrientationConstraint(l, i, sum);
l.Q[i] = sum;
}
}, phases.size() > 1 ? 1000 : ~size_t(0)); // one phase = plain sequential sweep
}
void applyPositionConstraint(const Level& l, uint32_t i, const vec3& q, vec3& o) {
if (l.ctype[i] == kPoint) {
o = l.cpos[i] - l.N[i] * glm::dot(l.N[i], l.cpos[i] - l.V[i]);
} else if (l.ctype[i] == kLine && !l.cfix.empty() && l.cfix[i]) { // a pinned corner on a closed guide
o = l.cpos[i] - l.N[i] * glm::dot(l.N[i], l.cpos[i] - l.V[i]);
} else if (l.ctype[i] == kLine) {
const vec3 perp = glm::cross(l.N[i], l.cdir[i]); // across the line, in the tangent plane
o -= perp * glm::dot(o - l.cpos[i], perp);
}
}
void smoothPositions(Level& l, int iterations) {
const auto& phases = l.phases;
for (int it = 0; it < iterations; ++it)
for (const auto& phase : phases)
parallelFor(phase.size(), [&](size_t b, size_t e) {
for (size_t k = b; k < e; ++k) {
const uint32_t i = phase[k];
const vec3 n = l.N[i], v = l.V[i], q = l.Q[i];
const float s = l.S[i];
vec3 sum = l.O[i];
float wsum = 0.0f;
for (uint32_t a = l.off[i]; a < l.off[i + 1]; ++a) {
const uint32_t j = l.adj[a];
const float w = l.w[a];
const vec3 qj = alignTo(q, n, l.Q[j], l.N[j]);
ivec2 i0, i1;
compatIndex(v, n, q, sum, s, l.V[j], l.N[j], qj, l.O[j], l.S[j], i0, i1);
const vec3 p0 = latticePoint(sum, q, glm::cross(n, q), s, i0);
const vec3 p1 = latticePoint(l.O[j], qj, glm::cross(l.N[j], qj), l.S[j], i1);
sum = (p0 * wsum + p1 * w) / (wsum + w);
wsum += w;
sum -= n * glm::dot(n, sum - v);
}
applyPositionConstraint(l, i, q, sum);
l.O[i] = positionRound(sum, q, n, v, s);
}
}, phases.size() > 1 ? 1000 : ~size_t(0)); // one phase = plain sequential sweep
}
// --- Extraction -----------------------------------------------------------------------------------------
struct UnionFind {
std::vector<uint32_t> parent;
explicit UnionFind(size_t n) : parent(n) { std::iota(parent.begin(), parent.end(), 0u); }
uint32_t find(uint32_t x) {
while (parent[x] != x) x = parent[x] = parent[parent[x]];
return x;
}
};
struct PolyMesh {
std::vector<vec3> P, N;
std::vector<uint8_t> feature; // per vertex: on a hard edge / border (1) or a corner (2)
std::vector<vec3> featureDir; // the line's direction (feature 1)
std::vector<std::vector<uint32_t>> faces;
size_t cornerCount() const {
size_t c = 0;
for (const auto& f : faces) c += f.size();
return c;
}
};
constexpr float kApartCos = -0.1f; // clusters whose normals are more than ~95 degrees apart don't merge
// Turns the fields on level `l` into a polygon mesh (faces wound counter-clockwise about the normals).
// Faces that are mostly mesh boundary (the outside of an open surface, the symmetry cut) are left out.
PolyMesh extractPolygons(const Level& l) {
const size_t n = l.size();
struct Link {
uint32_t i, j;
float cost;
};
std::vector<Link> collapse, links;
for (uint32_t i = 0; i < n; ++i)
for (uint32_t a = l.off[i]; a < l.off[i + 1]; ++a) {
const uint32_t j = l.adj[a];
if (j <= i) continue;
const vec3 qj = alignTo(l.Q[i], l.N[i], l.Q[j], l.N[j]);
ivec2 i0, i1;
const float err = compatIndex(l.V[i], l.N[i], l.Q[i], l.O[i], l.S[i], l.V[j], l.N[j], qj, l.O[j], l.S[j], i0, i1);
const float s = 0.5f * (l.S[i] + l.S[j]);
if (err > 0.25f * s * s) continue; // the two lattices disagree here (near a singularity)
const ivec2 d = i0 - i1;
const int l1 = std::abs(d.x) + std::abs(d.y);
if (l1 == 0) collapse.push_back({i, j, glm::length(l.O[i] - l.O[j])});
else if (l1 == 1) links.push_back({i, j, 0.0f});
}
std::sort(collapse.begin(), collapse.end(), [](const Link& a, const Link& b) { return a.cost < b.cost; });
// Merge vertices that sit on the same lattice corner, unless that drags a cluster too far.
// Clusters facing apart (the two sides of a part thinner than a quad, the faces either side of a sharp
// rim) stay apart: the vertices become neighbours instead, so the thin part keeps its thickness.
UnionFind uf(n);
std::vector<vec3> sum(l.O), nsum(n);
for (uint32_t i = 0; i < n; ++i) nsum[i] = l.N[i] * std::max(l.A[i], 1e-30f);
std::vector<float> cnt(n, 1.0f);
for (const Link& c : collapse) {
uint32_t a = uf.find(c.i), b = uf.find(c.j);
if (a == b) continue;
const float s = 0.5f * (l.S[c.i] + l.S[c.j]);
if (glm::length(sum[a] / cnt[a] - sum[b] / cnt[b]) > 0.45f * s) continue;
if (glm::dot(safeNormalize(nsum[a]), safeNormalize(nsum[b])) < kApartCos) {
links.push_back({c.i, c.j, 0.0f});
continue;
}
if (cnt[a] < cnt[b]) std::swap(a, b);
uf.parent[b] = a;
sum[a] += sum[b];
nsum[a] += nsum[b];
cnt[a] += cnt[b];
}
std::vector<uint32_t> cluster(n, kNone);
PolyMesh pm;
std::vector<vec3> qOf;
std::vector<float> area, scale;
std::vector<uint8_t> boundary, feature; // feature: 1 = on a hard edge / border line, 2 = a corner
std::vector<vec3> featureDir;
for (uint32_t i = 0; i < n; ++i) {
const uint32_t r = uf.find(i);
if (cluster[r] == kNone) {
cluster[r] = uint32_t(pm.P.size());
pm.P.push_back(sum[r] / cnt[r]);
pm.N.push_back(vec3(0.0f));
qOf.push_back(l.Q[i]);
area.push_back(0.0f);
scale.push_back(0.0f);
boundary.push_back(0);
feature.push_back(0);
featureDir.push_back(vec3(0.0f));
}
const uint32_t c = cluster[r];
cluster[i] = c;
if (l.ctype[i] == kPoint) feature[c] = 2;
else if (l.ctype[i] == kLine && feature[c] == 0) feature[c] = 1, featureDir[c] = l.cdir[i];
pm.N[c] += l.N[i] * l.A[i];
area[c] += l.A[i];
scale[c] = std::max(scale[c], l.S[i]);
boundary[c] |= l.boundary[i];
}
const size_t nc = pm.P.size();
for (uint32_t c = 0; c < nc; ++c) pm.N[c] = safeNormalize(pm.N[c]);
// Graph edges between clusters one lattice step apart; tiny clusters (stray vertices at singularities) go.
std::vector<std::vector<uint32_t>> adj(nc);
std::vector<uint8_t> alive(nc, 1);
for (uint32_t c = 0; c < nc; ++c)
if (area[c] < 0.04f * scale[c] * scale[c]) alive[c] = 0;
for (const Link& e : links) {
const uint32_t a = cluster[e.i], b = cluster[e.j];
if (a == b || !alive[a] || !alive[b]) continue;
adj[a].push_back(b);
adj[b].push_back(a);
}
for (auto& a : adj) {
std::sort(a.begin(), a.end());
a.erase(std::unique(a.begin(), a.end()), a.end());
}
auto removeEdge = [&](uint32_t a, uint32_t b) {
adj[a].erase(std::remove(adj[a].begin(), adj[a].end(), b), adj[a].end());
adj[b].erase(std::remove(adj[b].begin(), adj[b].end(), a), adj[b].end());
};
auto hasEdge = [&](uint32_t a, uint32_t b) { return std::binary_search(adj[a].begin(), adj[a].end(), b); };
auto len2 = [&](uint32_t a, uint32_t b) { return glm::dot(pm.P[a] - pm.P[b], pm.P[a] - pm.P[b]); };
// An edge running along a hard edge or border (both ends on it, in its direction): the feature's loop.
auto alongFeature = [&](uint32_t a, uint32_t b) {
if (!feature[a] || !feature[b]) return false;
const vec3 d = safeNormalize(pm.P[b] - pm.P[a]);
return (feature[a] == 1 && std::abs(glm::dot(d, featureDir[a])) > 0.9f) ||
(feature[b] == 1 && std::abs(glm::dot(d, featureDir[b])) > 0.9f);
};
// A quad lattice has no 3-cycles: drop the longest edge of each (a diagonal from a lattice mismatch), but
// keep the edges along features (across a part thinner than a quad the diagonal can be the shorter).
for (int round = 0; round < 8; ++round) {
std::vector<std::pair<uint32_t, uint32_t>> drop;
for (uint32_t u = 0; u < nc; ++u)
for (uint32_t v : adj[u]) {
if (v <= u) continue;
for (uint32_t w : adj[u]) {
if (w <= v || !hasEdge(v, w)) continue;
const std::pair<uint32_t, uint32_t> sides[3] = {{u, v}, {v, w}, {u, w}};
std::pair<uint32_t, uint32_t> e{u, v};
float best = -1.0f;
for (int pass = 0; pass < 2 && best < 0.0f; ++pass)
for (auto [a, b] : sides)
if ((pass == 1 || !alongFeature(a, b)) && len2(a, b) > best) best = len2(a, b), e = {a, b};
drop.push_back(e);
}
}
if (drop.empty()) break;
for (auto [a, b] : drop)
if (hasEdge(a, b)) removeEdge(a, b);
}
std::vector<std::vector<uint32_t>> faces;
for (int round = 0; round < 16; ++round) {
// Dangling vertices (fewer than two edges) can't bound a face.
std::vector<uint32_t> stack;
for (uint32_t u = 0; u < nc; ++u)
if (adj[u].size() == 1) stack.push_back(u);
while (!stack.empty()) {
const uint32_t u = stack.back();
stack.pop_back();
if (adj[u].size() != 1) continue;
const uint32_t v = adj[u][0];
removeEdge(u, v);
if (adj[v].size() == 1) stack.push_back(v);
}
// Rotation system: neighbours counter-clockwise about the vertex normal.
std::vector<std::vector<uint32_t>> ring(nc);
std::vector<uint32_t> heOff(nc + 1, 0);
for (uint32_t u = 0; u < nc; ++u) {
const vec3 nn = pm.N[u];
vec3 q = qOf[u] - nn * glm::dot(nn, qOf[u]);
q = glm::length(q) > 1e-6f ? glm::normalize(q) : anyTangent(nn);
const vec3 t = glm::cross(nn, q);
std::vector<std::pair<float, uint32_t>> ang;
for (uint32_t v : adj[u]) {
const vec3 d = pm.P[v] - pm.P[u];
ang.push_back({std::atan2(glm::dot(d, t), glm::dot(d, q)), v});
}
std::sort(ang.begin(), ang.end());
for (auto& [a, v] : ang) ring[u].push_back(v);
heOff[u + 1] = heOff[u] + uint32_t(ring[u].size());
}
auto slot = [&](uint32_t u, uint32_t v) { // index of v in u's ring
const auto& r = ring[u];
return uint32_t(std::find(r.begin(), r.end(), v) - r.begin());
};
std::vector<uint8_t> used(heOff[nc], 0);
faces.clear();
std::vector<std::pair<uint32_t, uint32_t>> bad;
for (uint32_t u0 = 0; u0 < nc; ++u0)
for (uint32_t k0 = 0; k0 < ring[u0].size(); ++k0) {
if (used[heOff[u0] + k0]) continue;
std::vector<uint32_t> face;
uint32_t u = u0, k = k0;
while (!used[heOff[u] + k]) {
used[heOff[u] + k] = 1;
face.push_back(u);
const uint32_t v = ring[u][k];
const uint32_t back = slot(v, u);
const uint32_t deg = uint32_t(ring[v].size());
k = (back + deg - 1) % deg; // next face edge: the neighbour before u, clockwise turn
u = v;
}
// An edge walked both ways in one face is a bridge, not a face side: drop it and retrace.
std::unordered_map<uint64_t, int> seen;
for (size_t a = 0; a < face.size(); ++a) {
const uint64_t key = edgeKey(face[a], face[(a + 1) % face.size()]);
if (++seen[key] == 2) bad.push_back({face[a], face[(a + 1) % face.size()]});
}
faces.push_back(std::move(face));
}
if (bad.empty() || round == 15) break;
for (auto [a, b] : bad)
if (std::find(adj[a].begin(), adj[a].end(), b) != adj[a].end()) removeEdge(a, b);
}
// Keep the faces; leave the outside of open surfaces open.
std::vector<uint32_t> remap(nc, kNone);
PolyMesh out;
for (auto& f : faces) {
if (f.size() < 3) continue;
if (f.size() >= 5) {
size_t onBoundary = 0;
for (uint32_t v : f) onBoundary += boundary[v];
if (onBoundary * 10 >= f.size() * 6) continue;
}
// Drop a face whose edge appears twice (left after the retrace limit).
bool twice = false;
{
std::unordered_map<uint64_t, int> seen;
for (size_t a = 0; a < f.size(); ++a)
if (++seen[edgeKey(f[a], f[(a + 1) % f.size()])] == 2) twice = true;
}
if (twice) continue;
for (uint32_t& v : f) {
if (remap[v] == kNone) {
remap[v] = uint32_t(out.P.size());
out.P.push_back(pm.P[v]);
out.N.push_back(pm.N[v]);
out.feature.push_back(feature[v]);
out.featureDir.push_back(featureDir[v]);
}
v = remap[v];
}
out.faces.push_back(std::move(f));
}
return out;
}
// Faces with six or more sides are cut along inside diagonals into quads (and at most one pentagon), so the
// quad split doesn't leave a star of six or more quads around one centre.
void splitLargeFaces(PolyMesh& pm) {
std::vector<std::vector<uint32_t>> out, todo = std::move(pm.faces);
std::unordered_map<uint64_t, int> edges; // existing edges: a diagonal must not duplicate one
for (const auto& f : todo)
for (size_t k = 0; k < f.size(); ++k) edges[edgeKey(f[k], f[(k + 1) % f.size()])] = 1;
while (!todo.empty()) {
std::vector<uint32_t> f = std::move(todo.back());
todo.pop_back();
const size_t n = f.size();
if (n <= 5) {
out.push_back(std::move(f));
continue;
}
// The face flattened onto its own plane.
vec3 nrm(0.0f), c(0.0f);
for (size_t k = 0; k < n; ++k) {
nrm += glm::cross(pm.P[f[k]], pm.P[f[(k + 1) % n]]);
c += pm.P[f[k]];
}
c /= float(n);
nrm = safeNormalize(nrm, pm.N[f[0]]);
const vec3 ax = anyTangent(nrm), ay = glm::cross(nrm, ax);
std::vector<glm::vec2> q(n);
float perimeter = 0.0f;
for (size_t k = 0; k < n; ++k) {
q[k] = {glm::dot(pm.P[f[k]] - c, ax), glm::dot(pm.P[f[k]] - c, ay)};
perimeter += glm::length(pm.P[f[k]] - pm.P[f[(k + 1) % n]]);
}
auto cross2 = [](glm::vec2 a, glm::vec2 b) { return a.x * b.y - a.y * b.x; };
auto segmentsCross = [&](glm::vec2 a, glm::vec2 b, glm::vec2 p, glm::vec2 r) {
const float d1 = cross2(b - a, p - a), d2 = cross2(b - a, r - a);
const float d3 = cross2(r - p, a - p), d4 = cross2(r - p, b - p);
return ((d1 > 0) != (d2 > 0)) && ((d3 > 0) != (d4 > 0));
};
auto inside = [&](glm::vec2 p) {
bool in = false;
for (size_t k = 0, l = n - 1; k < n; l = k++)
if ((q[k].y > p.y) != (q[l].y > p.y) && p.x < (q[l].x - q[k].x) * (p.y - q[k].y) / (q[l].y - q[k].y) + q[k].x)
in = !in;
return in;
};
float best = std::numeric_limits<float>::max();
size_t bi = 0, bj = 0;
for (size_t i = 0; i < n; ++i)
for (size_t j = i + 3; j < n; ++j) {
const size_t a = j - i + 1, b = n - (j - i) + 1;
if (b < 4 || f[i] == f[j] || edges.count(edgeKey(f[i], f[j]))) continue;
bool ok = inside(0.5f * (q[i] + q[j]));
for (size_t k = 0; k < n && ok; ++k) {
const size_t l = (k + 1) % n;
if (k == i || l == i || k == j || l == j) continue;
if (segmentsCross(q[i], q[j], q[k], q[l])) ok = false;
}
if (!ok) continue;
// Short diagonals and even (quad-friendly) halves first.
float score = glm::length(pm.P[f[i]] - pm.P[f[j]]) / perimeter;
if (a % 2) score += 0.25f;
if (b % 2) score += 0.25f;
score += 0.02f * float(std::max(a, b) - std::min(a, b));
if (score < best) best = score, bi = i, bj = j;
}
if (best == std::numeric_limits<float>::max()) {
out.push_back(std::move(f));
continue;
}
edges[edgeKey(f[bi], f[bj])] = 1;
std::vector<uint32_t> fa(f.begin() + long(bi), f.begin() + long(bj) + 1), fb(f.begin() + long(bj), f.end());
fb.insert(fb.end(), f.begin(), f.begin() + long(bi) + 1);
todo.push_back(std::move(fa));
todo.push_back(std::move(fb));
}
pm.faces = std::move(out);
}
// --- Quads, relaxation, attributes ----------------------------------------------------------------------
using qr::QuadMesh;
// Every n-sided face becomes n quads (corner, edge midpoint, centre, edge midpoint).
QuadMesh splitIntoQuads(const PolyMesh& pm) {
QuadMesh q;
q.P = pm.P;
q.feature = pm.feature;
std::unordered_map<uint64_t, uint32_t> mids;
auto mid = [&](uint32_t a, uint32_t b) {
auto [it, inserted] = mids.try_emplace(edgeKey(a, b), uint32_t(q.P.size()));
if (inserted) {
q.P.push_back(0.5f * (pm.P[a] + pm.P[b]));
// The middle of an edge running along a feature line is on it too.
const vec3 d = safeNormalize(pm.P[b] - pm.P[a]);
q.feature.push_back(pm.feature[a] && pm.feature[b] &&
((pm.feature[a] == 1 && std::abs(glm::dot(d, pm.featureDir[a])) > 0.9f) ||
(pm.feature[b] == 1 && std::abs(glm::dot(d, pm.featureDir[b])) > 0.9f)));
}
return it->second;
};
for (const auto& f : pm.faces) {
const size_t n = f.size();
vec3 c(0.0f);
for (uint32_t v : f) c += pm.P[v];
const uint32_t center = uint32_t(q.P.size());
q.P.push_back(c / float(n));
q.feature.push_back(0);
for (size_t k = 0; k < n; ++k) {
const uint32_t prev = f[(k + n - 1) % n], cur = f[k], next = f[(k + 1) % n];
q.quads.push_back({cur, mid(cur, next), center, mid(prev, cur)});
}
}
return q;
}
// A vertex inside the surface with only two quads (a "doublet", left where a two-sided face met a corner)
// adds nothing: the two quads become one. Unused vertices are dropped afterwards.
void removeDoublets(QuadMesh& q) {
for (int pass = 0; pass < 6; ++pass) {
const size_t nv = q.P.size();
std::vector<std::vector<uint32_t>> vq(nv);
for (uint32_t f = 0; f < q.quads.size(); ++f)
for (int k = 0; k < 4; ++k) vq[q.quads[f][k]].push_back(f);
std::vector<uint8_t> dead(q.quads.size(), 0), touched(nv, 0);
auto rotated = [&](uint32_t f, uint32_t v) {
glm::uvec4 r = q.quads[f];
for (int k = 0; k < 4 && r.x != v; ++k) r = {r.y, r.z, r.w, r.x};
return r;
};
bool any = false;
for (uint32_t v = 0; v < nv; ++v) {
if (vq[v].size() != 2 || touched[v]) continue;
const uint32_t fa = vq[v][0], fb = vq[v][1];
const glm::uvec4 A = rotated(fa, v), B = rotated(fb, v); // (v, a, x, c) and (v, c, y, a)
if (A.x != v || B.x != v || B.y != A.w || B.w != A.y || A.z == B.z) continue;
bool busy = false;
for (int k = 0; k < 4; ++k) busy |= touched[A[k]] || touched[B[k]];
if (busy) continue;
q.quads[fa] = {A.y, A.z, A.w, B.z};
dead[fb] = 1;
for (int k = 0; k < 4; ++k) touched[A[k]] = touched[B[k]] = 1;
any = true;
}
if (!any) break;
size_t w = 0;
for (size_t f = 0; f < q.quads.size(); ++f)
if (!dead[f]) q.quads[w++] = q.quads[f];
q.quads.resize(w);
}
std::vector<uint32_t> remap(q.P.size(), kNone);
std::vector<vec3> P;
std::vector<uint8_t> feature;
for (auto& f : q.quads)
for (int k = 0; k < 4; ++k) {
if (remap[f[k]] == kNone) {
remap[f[k]] = uint32_t(P.size());
P.push_back(q.P[f[k]]);
feature.push_back(q.feature[f[k]]);
}
f[k] = remap[f[k]];
}
q.P.swap(P);
q.feature.swap(feature);
}
struct Snapper {
const TriangleBVH* surface = nullptr;
const SegmentBVH* boundary = nullptr; // open edges of the source (incl. the symmetry cut)
const SegmentBVH* borders = nullptr; // face group borders (Follow Face Groups) and hard edges
const SegmentBVH* corners = nullptr; // where several of those meet (as zero-length segments)
float reach = 1.0f;
const SegmentBVH* guides = nullptr; // QRemesh Guides: only the loops' own vertices snap to them
};
// Tangential relaxation on the source surface; vertices on open edges stay on the source's open edges, those
// on face group borders on the borders.
void relax(QuadMesh& q, const Snapper& snap, int iterations, float edge, const QRemeshProgress& progress, float p0,
float p1, bool& cancelled) {
const size_t nv = q.P.size();
// Neighbours and open edges from the quads.
std::unordered_map<uint64_t, int> edgeUse;
for (const auto& f : q.quads)
for (int k = 0; k < 4; ++k) ++edgeUse[edgeKey(f[k], f[(k + 1) % 4])];
std::vector<std::vector<uint32_t>> nb(nv);
std::vector<uint8_t> open(nv, 0);
for (auto [key, uses] : edgeUse) {
const uint32_t a = uint32_t(key >> 32), b = uint32_t(key & 0xffffffffu);
nb[a].push_back(b);
nb[b].push_back(a);
if (uses == 1) open[a] = open[b] = 2; // 2 = open-edge vertex, 1 = face group border vertex
}
std::vector<std::vector<uint32_t>> openNb(nv);
for (auto [key, uses] : edgeUse) {
if (uses != 1) continue;
const uint32_t a = uint32_t(key >> 32), b = uint32_t(key & 0xffffffffu);
openNb[a].push_back(b);
openNb[b].push_back(a);
}
auto project = [&](uint32_t v, const vec3& p, vec3& normal) {
SurfaceHit hit;
if (open[v] == 2 && snap.boundary && snap.boundary->closestPoint(p, snap.reach, hit)) {
normal = vec3(0.0f);
return hit.position;
}
if (open[v] == 1) {
SurfaceHit g;
const bool onBorder = snap.borders && snap.borders->closestPoint(p, snap.reach, hit);
const bool onGuide = snap.guides && snap.guides->closestPoint(p, onBorder ? hit.distance : snap.reach, g);
if (onBorder || onGuide) {
normal = vec3(0.0f);
return onGuide ? g.position : hit.position;
}
}
if (snap.surface->closestPoint(p, snap.reach, hit)) {
normal = snap.surface->faceNormal(hit.prim);
return hit.position;
}
normal = vec3(0.0f);
return p;
};
std::vector<vec3> normal(nv, vec3(0.0f));
parallelFor(nv, [&](size_t b, size_t e) {
for (size_t v = b; v < e; ++v) q.P[v] = project(uint32_t(v), q.P[v], normal[v]);
});
// Face group-border vertices: within a fifth of an edge of a border.
// Vertices on a guide's loop are the ones extracted on it (features): a vertex merely near a guide stays free.
if (snap.borders || snap.guides)
for (uint32_t v = 0; v < nv; ++v) {
SurfaceHit hit;
if (open[v] == 0 && (q.feature[v] || (snap.borders && snap.borders->closestPoint(q.P[v], 0.2f * edge, hit))))
open[v] = 1;
}
// Corners of the source (a box's, a thin slab's) each pin their nearest quad vertex, so they stay sharp.
std::vector<uint8_t> pinned(nv, 0);
if (snap.corners) {
// Closest pairs first, each corner and each vertex used once (a thin part's corners are close together).
struct Pair {
float d;
uint32_t corner, v;
vec3 at;
};
std::vector<Pair> pairs;
for (uint32_t v = 0; v < nv; ++v) {
SurfaceHit hit;
if (snap.corners->closestPoint(q.P[v], 0.75f * edge, hit)) pairs.push_back({hit.distance, hit.prim, v, hit.position});
}
std::sort(pairs.begin(), pairs.end(), [](const Pair& a, const Pair& b) { return a.d < b.d; });
std::unordered_map<uint32_t, uint8_t> cornerUsed;
for (const Pair& p : pairs) {
if (pinned[p.v] || cornerUsed[p.corner]) continue;
cornerUsed[p.corner] = 1;
pinned[p.v] = 1;
q.P[p.v] = p.at;
if (open[p.v] == 0) open[p.v] = 1;
}
}
std::vector<std::vector<uint32_t>> borderNb(nv);
for (uint32_t v = 0; v < nv; ++v)
if (open[v] == 1)
for (uint32_t u : nb[v])
if (open[u] == 1) borderNb[v].push_back(u);
std::vector<vec3> next(nv);
for (int it = 0; it < iterations; ++it) {
parallelFor(nv, [&](size_t b, size_t e) {
for (size_t v = b; v < e; ++v) {
const auto& ring = open[v] == 2 ? openNb[v] : open[v] == 1 && borderNb[v].size() == 2 ? borderNb[v] : nb[v];
if (pinned[v] || ring.empty() || (open[v] == 1 && borderNb[v].size() != 2)) {
next[v] = q.P[v];
continue;
}
vec3 avg(0.0f);
for (uint32_t u : ring) avg += q.P[u];
avg /= float(ring.size());
vec3 d = avg - q.P[v];
if (open[v] == 0) d -= normal[v] * glm::dot(normal[v], d);
next[v] = q.P[v] + 0.6f * d;
}
});
parallelFor(nv, [&](size_t b, size_t e) {
for (size_t v = b; v < e; ++v)
if (!pinned[v]) q.P[v] = project(uint32_t(v), next[v], normal[v]);
});
if (progress && !progress(p0 + (p1 - p0) * float(it + 1) / float(std::max(iterations, 1)))) {
cancelled = true;
return;
}
}
}
// Connected pieces of the working surface (triangles sharing vertices): the piece of each triangle.
std::vector<uint32_t> pieceOfTriangles(const WorkMesh& m, size_t& count) {
UnionFind uf(m.P.size());
for (const glm::uvec3& t : m.T) {
const uint32_t a = uf.find(t.x);
if (const uint32_t b = uf.find(t.y); b != a) uf.parent[b] = a;
if (const uint32_t c = uf.find(t.z), r = uf.find(t.x); c != r) uf.parent[c] = r;
}
std::vector<uint32_t> id(m.P.size(), kNone), piece(m.T.size());
count = 0;
for (size_t t = 0; t < m.T.size(); ++t) {
const uint32_t r = uf.find(m.T[t].x);
if (id[r] == kNone) id[r] = uint32_t(count++);
piece[t] = id[r];
}
return piece;
}
// Sorts the pieces into meshes: piece i goes to mesh slot[i] (kNone: left out). Vertices keep their order
// (the hierarchy and the field sweeps follow it, so a mesh remeshes as those pieces would alone).
std::vector<WorkMesh> gatherPieces(const WorkMesh& m, const std::vector<uint32_t>& piece, const std::vector<uint32_t>& slot,
size_t slots) {
std::vector<WorkMesh> out(slots);
std::vector<uint32_t> slotOfVertex(m.P.size(), kNone), local(m.P.size(), kNone);
for (size_t t = 0; t < m.T.size(); ++t)
if (const uint32_t s = slot[piece[t]]; s != kNone)
for (int k = 0; k < 3; ++k) slotOfVertex[m.T[t][k]] = s;
for (uint32_t v = 0; v < m.P.size(); ++v) {
const uint32_t s = slotOfVertex[v];
if (s == kNone) continue;
local[v] = uint32_t(out[s].P.size());
out[s].P.push_back(m.P[v]);
if (!m.color.empty()) out[s].color.push_back(m.color[v]);
}
for (size_t t = 0; t < m.T.size(); ++t) {
const uint32_t s = slot[piece[t]];
if (s == kNone) continue;
const glm::uvec3 tri = m.T[t];
out[s].T.push_back({local[tri.x], local[tri.y], local[tri.z]});
out[s].group.push_back(m.group[t]);
}
return out;
}
// How far the surface is from its own mirror image about the plane (axis coordinate = c): the distances of
// mirrored sample points (triangle centres) to the surface, area-weighted mean and 98th percentile.
struct MirrorFit {
float mean = 0.0f, high = 0.0f;
};
MirrorFit mirrorFit(const TriangleBVH& surface, const WorkMesh& m, int axis, float c, float reach) {
const size_t step = std::max<size_t>(1, m.T.size() / 20000);
const size_t n = (m.T.size() + step - 1) / step;
std::vector<std::pair<float, float>> d(n); // (distance, area)
parallelFor(n, [&](size_t b, size_t e) {
for (size_t i = b; i < e; ++i) {
const glm::uvec3 t = m.T[i * step];
vec3 p = (m.P[t.x] + m.P[t.y] + m.P[t.z]) / 3.0f;
p[axis] = 2.0f * c - p[axis];
SurfaceHit hit;
d[i] = {surface.closestPoint(p, reach, hit) ? hit.distance : reach,
0.5f * glm::length(glm::cross(m.P[t.y] - m.P[t.x], m.P[t.z] - m.P[t.x]))};
}
});
double sum = 0.0, area = 0.0;
for (auto [dist, a] : d) sum += double(dist) * a, area += a;
MirrorFit f;
if (area <= 0.0) return f;
f.mean = float(sum / area);
std::sort(d.begin(), d.end());
double acc = 0.0;
for (auto [dist, a] : d) {
acc += a;
f.high = dist;
if (acc >= 0.98 * area) break;
}
return f;
}
// One piece of the working surface, remeshed: its quads (empty when the lattice found none), the vertices on
// the symmetry cut, and the lattice size used.
struct PieceResult {
QuadMesh mesh;
std::vector<uint8_t> seam;
float spacing = 0.0f;
int attempts = 0;
size_t guideDefects = 0; // see guideDefects
};
// What went wrong round the QRemesh Guides in a piece's result: vertices on a loop (or a curve from the seam to
// the seam) whose edge loop along it breaks, a loop not followed all the way, and fans (7 or more edges, a seam
// vertex's mirror image counted) within `reach` of a guide. Zero when all is well.
size_t guideDefects(const QuadMesh& q, const SegmentBVH& guides, const std::vector<ClosedGuide>& pinned, int axis,
float edge, float reach) {
const size_t nv = q.P.size();
std::vector<std::vector<uint32_t>> nb(nv);
{
std::unordered_map<uint64_t, uint8_t> seen;
for (const auto& f : q.quads)
for (int k = 0; k < 4; ++k) {
const uint32_t a = f[k], b = f[(k + 1) % 4];
if (seen.emplace(edgeKey(a, b), 1).second) nb[a].push_back(b), nb[b].push_back(a);
}
}
auto onSeam = [&](uint32_t v) { return axis >= 0 && std::abs(q.P[v][axis]) < 0.01f * edge; };
size_t defects = 0;
for (uint32_t v = 0; v < nv; ++v) {
const size_t k = nb[v].size();
SurfaceHit hit;
if ((onSeam(v) ? 2 * k - 2 : k) >= 7 && guides.closestPoint(q.P[v], reach, hit)) ++defects;
}
for (const ClosedGuide& c : pinned) {
if (!c.lines || c.steps <= 0.0f) continue;
std::vector<uint8_t> on(nv, 0);
for (uint32_t v = 0; v < nv; ++v) {
SurfaceHit hit;
on[v] = q.feature[v] && c.bvh.closestPoint(q.P[v], 0.1f * edge, hit);
}
double along = 0.0;
for (uint32_t v = 0; v < nv; ++v) {
if (!on[v]) continue;
int deg = 0;
for (uint32_t u : nb[v])
if (on[u]) ++deg, along += 0.5 * double(glm::length(q.P[u] - q.P[v]));
if (deg != 2 && !(deg == 1 && !c.loop && onSeam(v))) ++defects;
}
if (along < 0.9 * double(c.length)) ++defects;
}
return defects;
}
// The field-aligned remesh of one connected piece to about `wantQuads` quads. False on cancel.
bool remeshPiece(WorkMesh work, int axis, double wantQuads, const QRemeshOptions& opt, float diag,
const std::vector<QRemeshGuide>& guides, const std::function<bool(float)>& report,
const std::function<void(const char*)>& mark, PieceResult& res) {
static const bool timing = std::getenv("SF_QREMESH_TIMING") != nullptr;
const QRemeshProgress progress = [&](float f) { return report(f); };
double area = 0.0;
for (const glm::uvec3& t : work.T) area += 0.5 * glm::length(glm::cross(work.P[t.y] - work.P[t.x], work.P[t.z] - work.P[t.x]));
// Coarse lattice spacing: the extracted faces (about target / 4 of them, each split into ~4 quads).
const double faces = std::max(4.0, wantQuads / 4.0);
float spacing = float(std::sqrt(area / faces));
const bool adaptive = opt.adaptive > 0.01f || !work.color.empty();
const float wantEdge = spacing / 4.0f; // about four graph vertices per lattice edge
// Surface the quads snap to (before any subdivision for density: same surface).
mark("prepare");
TriangleBVH surface;
surface.build(work.P, work.T);
mark("surface bvh");
if (!report(0.05f)) return false;
std::vector<std::pair<vec3, vec3>> boundarySegs, borderSegs, guideSegs;
std::vector<uint8_t> boundaryIsCut;
work = refineLongEdges(std::move(work), 1.5f * wantEdge, std::max<size_t>(4'000'000, work.T.size()));
std::vector<Level> levels;
std::vector<ClosedGuide> closedGuides;
const float sharpCos = opt.detectEdges ? std::cos(glm::radians(50.0f)) : 2.0f;
mark("refine");
levels.push_back(buildFinest(work, opt.keepGroups, sharpCos, boundarySegs, boundaryIsCut, borderSegs, axis));
if (!guides.empty()) {
// The flow follows a curve over 0.5 (Guide Strength 0) to 6 quads (1) to each side; a quad is half the
// lattice spacing (each extracted face splits into four).
const float strength = std::clamp(opt.guideStrength, 0.0f, 1.0f);
applyGuides(levels[0], guides, spacing * (0.25f + 2.75f * strength), axis, guideSegs, closedGuides);
mark("guides");
}
mark("finest level");
if (!report(0.10f)) return false;
// Hierarchy down to a few vertices; fields are solved from the top to the finest level dense enough.
while (levels.back().size() > 64 && levels.size() < 40) {
Level c;
if (!downsample(levels.back(), c)) break;
if (c.size() > levels.back().size() * 95 / 100) {
levels.push_back(std::move(c));
break;
}
levels.push_back(std::move(c));
}
mark("hierarchy");
size_t base = 0;
while (base + 1 < levels.size() && levels[base + 1].meanEdge <= wantEdge) ++base;
if (!report(0.20f)) return false;
for (size_t i = base; i < levels.size(); ++i) computePhases(levels[i]);
// Orientation field, coarse to fine.
Rng rng(opt.seed);
{
Level& top = levels.back();
top.Q.resize(top.size());
for (uint32_t i = 0; i < top.size(); ++i) {
const vec3 t0 = anyTangent(top.N[i]), t1 = glm::cross(top.N[i], t0);
const float a = rng.next() * 6.2831853f;
top.Q[i] = t0 * std::cos(a) + t1 * std::sin(a);
applyOrientationConstraint(top, i, top.Q[i]);
}
}
for (size_t li = levels.size(); li-- > base;) {
Level& l = levels[li];
if (li + 1 < levels.size()) {
const Level& c = levels[li + 1];
l.Q.resize(l.size());
for (uint32_t i = 0; i < l.size(); ++i) {
const vec3 q = c.Q[l.up[i]];
const vec3 p = q - l.N[i] * glm::dot(l.N[i], q);
l.Q[i] = glm::length(p) > 1e-6f ? glm::normalize(p) : anyTangent(l.N[i]);
applyOrientationConstraint(l, i, l.Q[i]);
}
}
smoothOrientations(l, li == base ? 12 : 10);
if (!report(0.20f + 0.20f * float(levels.size() - li) / float(levels.size() - base))) return false;
}
// Scale field on the base level: curvature (Size Variation) and vertex paint density, then normalised to the
// wanted number of faces and passed up the hierarchy.
Level& L = levels[base];
std::vector<float> rel(L.size(), 1.0f); // relative edge length
if (opt.adaptive > 0.01f) {
// Curvature: normal change per length (-1 = unknown, filled in from the neighbours).
std::vector<float> k(L.size(), -1.0f);
for (uint32_t i = 0; i < L.size(); ++i) {
if (L.ctype[i] != kFree) continue; // a feature's normal is the average of two sides
float s = 0.0f;
int c = 0;
for (uint32_t a = L.off[i]; a < L.off[i + 1]; ++a) {
const uint32_t j = L.adj[a];
const float d = glm::length(L.V[i] - L.V[j]);
// Normals jumping across a hard edge or a group border are features with their own loops, not
// curvature to pack quads into.
if (L.ctype[j] != kFree || glm::dot(L.N[i], L.N[j]) < sharpCos) continue;
if (d > 0.0f) s += glm::length(L.N[i] - L.N[j]) / d, ++c;
}
if (c) k[i] = s / float(c);
}
for (int it = 0; it < 6; ++it) {
std::vector<float> nk = k;
for (uint32_t i = 0; i < L.size(); ++i) {
float s = std::max(k[i], 0.0f);
int c = k[i] >= 0.0f;
for (uint32_t a = L.off[i]; a < L.off[i + 1]; ++a)
if (k[L.adj[a]] >= 0.0f) s += k[L.adj[a]], ++c;
nk[i] = c ? s / float(c) : -1.0f;
}
k.swap(nk);
}
// Relative to the median, but never finer than a bend of ~11 degrees per quad: flat models stay even.
std::vector<float> sorted;
for (float x : k)
if (x >= 0.0f) sorted.push_back(x);
float ref = 0.2f / spacing;
if (!sorted.empty()) {
std::nth_element(sorted.begin(), sorted.begin() + long(sorted.size() / 2), sorted.end());
ref = std::max(ref, sorted[sorted.size() / 2]);
}
for (uint32_t i = 0; i < L.size(); ++i)
rel[i] = k[i] < 0.0f ? 1.0f : std::clamp(std::pow(std::max(k[i], 1e-9f) / ref, -0.6f * opt.adaptive), 0.45f, 2.2f);
}
if (!L.color.empty())
for (uint32_t i = 0; i < L.size(); ++i) {
const vec3 c = L.color[i];
const float red = std::clamp(c.x - std::max(c.y, c.z), 0.0f, 1.0f);
const float blue = std::clamp(c.z - std::max(c.x, c.y), 0.0f, 1.0f);
rel[i] *= std::pow(2.0f, blue - red); // pure red: half the edge (4x the quads), pure blue: double
}
if (adaptive) // smooth the log of the size so it changes gradually
for (int it = 0; it < 8; ++it) {
std::vector<float> lr(L.size());
for (uint32_t i = 0; i < L.size(); ++i) {
float s = std::log(rel[i]);
int c = 1;
for (uint32_t a = L.off[i]; a < L.off[i + 1]; ++a) s += std::log(rel[L.adj[a]]), ++c;
lr[i] = std::exp(s / float(c));
}
rel.swap(lr);
}
auto setScale = [&](float sp) {
double want = 0.0;
for (uint32_t i = 0; i < L.size(); ++i) want += double(L.A[i]) / double(rel[i] * rel[i]);
const float c = float(std::sqrt(want / faces)) * (sp / spacing);
L.S.resize(L.size());
for (uint32_t i = 0; i < L.size(); ++i) L.S[i] = c * rel[i];
if (!closedGuides.empty()) {
closedGuideSize(L, L.S, closedGuides, 2.0f * c);
for (size_t li = base; li < levels.size(); ++li) pinClosedGuides(levels[li], closedGuides);
}
for (size_t li = base + 1; li < levels.size(); ++li) {
const Level& f = levels[li - 1];
Level& cl = levels[li];
std::vector<double> s(cl.size(), 0.0), a(cl.size(), 0.0);
for (uint32_t i = 0; i < f.size(); ++i) s[f.up[i]] += double(f.S[i]) * f.A[i], a[f.up[i]] += f.A[i];
cl.S.resize(cl.size());
for (uint32_t i = 0; i < cl.size(); ++i) cl.S[i] = a[i] > 0.0 ? float(s[i] / a[i]) : c;
}
};
// Position field and extraction; the lattice size is corrected until the quad count is near the target.
PolyMesh poly;
QuadMesh qm;
float sp = spacing;
for (int attempt = 0; attempt < 4; ++attempt) {
setScale(sp);
Level& top = levels.back();
top.O = top.V;
for (uint32_t i = 0; i < top.size(); ++i) applyPositionConstraint(top, i, top.Q[i], top.O[i]);
for (size_t li = levels.size(); li-- > base;) {
Level& l = levels[li];
if (li + 1 < levels.size()) {
const Level& c = levels[li + 1];
l.O.resize(l.size());
for (uint32_t i = 0; i < l.size(); ++i) {
const vec3 o = c.O[l.up[i]];
l.O[i] = o - l.N[i] * glm::dot(l.N[i], o - l.V[i]);
}
}
smoothPositions(l, li == base ? 10 : 10);
}
if (!report(0.45f + 0.1f * float(attempt))) return false;
poly = extractPolygons(L);
if (timing) {
std::map<size_t, size_t> sizes;
for (const auto& f : poly.faces) ++sizes[f.size()];
std::fprintf(stderr, "faces:");
for (auto [k, c] : sizes) std::fprintf(stderr, " %zu:%zu", k, c);
std::fprintf(stderr, "\n");
}
splitLargeFaces(poly);
qm = splitIntoQuads(poly);
removeDoublets(qm);
res.attempts = attempt + 1;
const double quads = double(qm.quads.size());
if (quads <= 0.0) break;
const double ratio = quads / wantQuads;
if (std::abs(ratio - 1.0) < 0.05 || attempt == 3) break;
sp *= float(std::sqrt(ratio));
}
if (qm.quads.empty()) return true; // no quads: the caller tries a finer lattice or keeps the piece as it is
if (!report(0.85f)) return false;
// Snap to the sculpt and relax.
SegmentBVH boundaryBvh, borderBvh, cornerBvh, guideBvh;
{
std::vector<vec3> c;
for (uint32_t i = 0; i < levels[0].size(); ++i)
if (levels[0].ctype[i] == kPoint) c.push_back(levels[0].V[i]);
cornerBvh.build(c, c);
std::vector<vec3> a, b;
for (auto& s : boundarySegs) a.push_back(s.first), b.push_back(s.second);
boundaryBvh.build(std::move(a), std::move(b));
a.clear(), b.clear();
for (auto& s : borderSegs) a.push_back(s.first), b.push_back(s.second);
borderBvh.build(std::move(a), std::move(b));
a.clear(), b.clear();
for (auto& s : guideSegs) a.push_back(s.first), b.push_back(s.second);
guideBvh.build(std::move(a), std::move(b));
}
Snapper snap{&surface, boundaryBvh.empty() ? nullptr : &boundaryBvh, borderBvh.empty() ? nullptr : &borderBvh,
cornerBvh.empty() ? nullptr : &cornerBvh, spacing * 4.0f + 1e-3f * diag, guideBvh.empty() ? nullptr : &guideBvh};
bool cancelled = false;
relax(qm, snap, std::max(opt.smoothIterations, 0), sp * 0.5f, progress, 0.85f, 0.95f, cancelled);
if (cancelled) return false;
// Vertices on the symmetry cut: open edges lying on the plane.
res.seam.assign(qm.P.size(), 0);
if (axis >= 0) {
std::unordered_map<uint64_t, int> edgeUse;
for (const auto& f : qm.quads)
for (int k = 0; k < 4; ++k) ++edgeUse[edgeKey(f[k], f[(k + 1) % 4])];
for (auto [key, uses] : edgeUse)
if (uses == 1) {
const uint32_t a = uint32_t(key >> 32), b = uint32_t(key & 0xffffffffu);
if (std::abs(qm.P[a][axis]) < 0.3f * sp && std::abs(qm.P[b][axis]) < 0.3f * sp) res.seam[a] = res.seam[b] = 1;
}
}
if (!guideBvh.empty())
res.guideDefects = guideDefects(qm, guideBvh, closedGuides, axis, 0.5f * sp, spacing * (0.25f + 2.75f * std::clamp(opt.guideStrength, 0.0f, 1.0f)) + sp);
res.spacing = sp;
res.mesh = std::move(qm);
return true;
}
} // namespace
bool qremesh(const Mesh& source, const QRemeshOptions& opt, Mesh& out, std::string& error,
const QRemeshProgress& progress, QRemeshStats* stats) {
const auto start = std::chrono::steady_clock::now();
static const bool timing = std::getenv("SF_QREMESH_TIMING") != nullptr; // stage times on stderr
auto report = [&](float f) {
if (timing)
std::fprintf(stderr, "qremesh %.2f: %.3f s\n", f,
std::chrono::duration<double>(std::chrono::steady_clock::now() - start).count());
if (progress && !progress(std::clamp(f, 0.0f, 1.0f))) {
error = "Quad Remesh cancelled";
return false;
}
return true;
};
auto mark = [&](const char* what) {
if (timing)
std::fprintf(stderr, " %-28s %.3f s\n", what,
std::chrono::duration<double>(std::chrono::steady_clock::now() - start).count());
};
if (source.triangleCount() == 0) {
error = "Quad Remesh: the Part is empty";
return false;
}
const int target = std::clamp(opt.targetQuads, 16, 2'000'000);
const int askedAxis = opt.symmetryAxis >= 0 && opt.symmetryAxis <= 2 ? opt.symmetryAxis : -1;
QRemeshStats st;
WorkMesh work;
work.P = source.positions;
work.T = source.triangles;
work.group.resize(work.T.size());
for (uint32_t t = 0; t < work.T.size(); ++t) work.group[t] = source.facegroupAt(t);
if (opt.useVertexPaint && source.hasColors()) work.color = source.colors;
const AABB box = source.bounds();
const float diag = glm::length(box.extent());
if (!(diag > 0.0f)) {
error = "Quad Remesh: the Part has no size";
return false;
}
// The whole sculpt as a query surface: the symmetry test, attributes, and the snap of mirrored vertices.
TriangleBVH full;
auto buildFull = [&] {
if (full.empty()) full.build(source.positions, source.triangles);
};
// Symmetry: find the mirror plane (the world's, or the model's own when it sits off the origin) and check
// the model really is mirror-symmetric about it; a model that isn't is remeshed without symmetry rather
// than having one side replaced by the other.
int axis = -1;
float center = 0.0f;
if (askedAxis >= 0) {
buildFull();
double totalArea = 0.0;
for (const glm::uvec3& t : work.T)
totalArea += 0.5 * glm::length(glm::cross(work.P[t.y] - work.P[t.x], work.P[t.z] - work.P[t.x]));
const float edge = float(std::sqrt(totalArea / double(target)));
std::vector<float> candidates;
if (opt.symmetryAuto) {
candidates = {0.0f, box.center()[askedAxis]};
double c = 0.0;
for (const glm::uvec3& t : work.T) {
const float a = 0.5f * glm::length(glm::cross(work.P[t.y] - work.P[t.x], work.P[t.z] - work.P[t.x]));
c += double(a) * double(work.P[t.x][askedAxis] + work.P[t.y][askedAxis] + work.P[t.z][askedAxis]) / 3.0;
}
if (totalArea > 0.0) candidates.push_back(float(c / totalArea));
} else {
candidates = {opt.symmetryCenter};
}
MirrorFit best;
best.mean = std::numeric_limits<float>::max();
for (float c : candidates) {
const MirrorFit f = mirrorFit(full, work, askedAxis, c, 0.25f * diag);
if (timing)
std::fprintf(stderr, " symmetry plane %.4f: mean %.4f, 98%% %.4f (edge %.4f)\n", c, f.mean, f.high, edge);
if (f.mean < best.mean) best = f, center = c;
}
st.symmetryCenter = center;
st.asymmetry = edge > 0.0f ? best.mean / edge : 0.0f;
if (best.mean <= 0.2f * edge && best.high <= 1.0f * edge) axis = askedAxis;
mark("symmetry plane");
}
st.symmetryAxis = askedAxis;
st.symmetryUsed = axis >= 0;
if (axis >= 0) {
for (vec3& p : work.P) p[axis] -= center;
work = cutAtPlane(work, axis, 1e-6f * diag);
if (work.T.empty()) {
error = "Quad Remesh: nothing on the positive side of the symmetry plane";
return false;
}
}
// QRemesh Guides in the working frame: snapped onto the sculpt as it is now (it may have changed since they
// were drawn) and, with symmetry, mirrored, so a curve drawn on either side guides both.
// A guide mostly off the surface (the Part was moved after it was drawn) is left out.
std::vector<QRemeshGuide> guides;
if (!opt.guides.empty()) buildFull();
for (const QRemeshGuide& g : opt.guides) {
QRemeshGuide s = g;
size_t on = 0;
for (vec3& p : s.points) {
SurfaceHit hit;
if (full.closestPoint(p, 0.05f * diag, hit)) p = hit.position, ++on;
if (axis >= 0) p[axis] -= center;
}
if (s.points.size() >= 2 && on * 2 > s.points.size()) guides.push_back(std::move(s));
else ++st.guidesSkipped;
}
st.guides = guides.size();
if (!guides.empty()) {
if (axis >= 0) {
// A curve that is its own mirror image (a loop round the mouth, across the middle) isn't doubled:
// the two copies would pin different corners on the same loop.
const size_t n = guides.size();
for (size_t i = 0; i < n; ++i) {
QRemeshGuide m = guides[i];
for (vec3& p : m.points) p[axis] = -p[axis];
std::vector<vec3> a, b;
for (size_t k = 0; k + 1 < guides[i].points.size(); ++k)
a.push_back(guides[i].points[k]), b.push_back(guides[i].points[k + 1]);
if (guides[i].closed) a.push_back(guides[i].points.back()), b.push_back(guides[i].points.front());
SegmentBVH self;
self.build(std::move(a), std::move(b));
double off = 0.0;
for (const vec3& p : m.points) {
SurfaceHit hit;
off += self.closestPoint(p, 0.05f * diag, hit) ? hit.distance : 0.05f * diag;
}
if (off / double(m.points.size()) > 0.004 * diag) guides.push_back(std::move(m));
}
// Only the +axis half is remeshed: each guide is cut at the plane. A loop across the middle becomes
// a curve from the seam to the seam (exactly on it at both ends), so its corners meet the seam's.
std::vector<QRemeshGuide> half;
for (const QRemeshGuide& g : guides) {
const size_t n = g.points.size();
const bool loop = g.closed && n > 2;
size_t start = 0; // a loop's walk starts on the far side, so no piece wraps round
if (loop)
while (start < n && g.points[start][axis] >= 0.0f) ++start;
if (loop && start == n) {
half.push_back(g);
continue;
}
QRemeshGuide run;
run.stroke = g.stroke;
auto flush = [&] {
if (run.points.size() >= 2) half.push_back(run);
run.points.clear();
};
if (g.points[start][axis] >= 0.0f) run.points.push_back(g.points[start]);
for (size_t k = 0, segs = loop ? n : n - 1; k < segs; ++k) {
const vec3 a = g.points[(start + k) % n], b = g.points[(start + k + 1) % n];
const bool ina = a[axis] >= 0.0f, inb = b[axis] >= 0.0f;
if (ina != inb) {
vec3 p = glm::mix(a, b, a[axis] / (a[axis] - b[axis]));
p[axis] = 0.0f;
run.points.push_back(p);
if (ina) flush();
}
if (inb) run.points.push_back(b);
}
flush();
}
guides = std::move(half);
}
}
// Small separate pieces (eyes, teeth, rivets: fewer than ~100 quads by their area) are remeshed on their
// own with a few dozen quads at least, so they don't vanish between the lattice corners of the big ones;
// the rest share one field (and the target, by curvature, as before).
const double wantQuads = double(target) / (axis >= 0 ? 2.0 : 1.0);
constexpr double kOwnFieldBelow = 100.0, kMinPieceQuads = 32.0;
std::vector<WorkMesh> parts;
std::vector<double> partArea, budget;
{
size_t count = 0;
const std::vector<uint32_t> piece = pieceOfTriangles(work, count);
st.pieces = count;
std::vector<double> pieceArea(count, 0.0);
double area = 0.0;
for (size_t t = 0; t < work.T.size(); ++t) {
const glm::uvec3 tri = work.T[t];
const double a = 0.5 * glm::length(glm::cross(work.P[tri.y] - work.P[tri.x], work.P[tri.z] - work.P[tri.x]));
pieceArea[piece[t]] += a;
area += a;
}
const double biggest = count ? *std::max_element(pieceArea.begin(), pieceArea.end()) : 0.0;
std::vector<uint8_t> small(count, 0);
double smallTotal = 0.0, bigArea = 0.0;
std::vector<double> smallBudget(count, 0.0);
for (size_t i = 0; i < count; ++i) {
const double share = wantQuads * pieceArea[i] / std::max(area, 1e-30);
if (share >= kOwnFieldBelow || pieceArea[i] >= biggest) {
bigArea += pieceArea[i];
continue;
}
small[i] = 1;
// Size Variation: a small piece is tightly curved, so it gets denser quads than its area alone gives
// (up to the 1 / 0.45^2 the curvature allows within a piece); sizes as the radius of a sphere of the
// same area, against the biggest piece's.
double weight = 1.0;
if (opt.adaptive > 0.01f)
weight = std::clamp(std::pow(std::sqrt(biggest / std::max(pieceArea[i], 1e-30)) / 4.0, 1.2 * double(opt.adaptive)),
1.0, 4.9);
smallBudget[i] = std::max(share * weight, kMinPieceQuads);
smallTotal += smallBudget[i];
}
if (smallTotal == 0.0) {
parts.push_back(std::move(work));
partArea.push_back(bigArea);
budget.push_back(wantQuads);
} else {
std::vector<uint32_t> slot(count, kNone);
size_t slots = bigArea > 0.0 ? 1 : 0;
if (bigArea > 0.0) {
partArea.push_back(bigArea);
budget.push_back(std::max(wantQuads - smallTotal, 0.5 * wantQuads));
}
for (size_t i = 0; i < count; ++i) {
if (!small[i]) {
slot[i] = 0;
continue;
}
slot[i] = uint32_t(slots++);
partArea.push_back(pieceArea[i]);
budget.push_back(smallBudget[i]);
}
parts = gatherPieces(work, piece, slot, slots);
}
work = WorkMesh{};
}
size_t totalTris = 0;
for (const WorkMesh& p : parts) totalTris += p.T.size();
if (!report(0.03f)) return false;
QuadMesh qm;
std::vector<uint8_t> seam;
size_t trisDone = 0;
for (size_t i = 0; i < parts.size(); ++i) {
const float f0 = 0.03f + 0.9f * float(trisDone) / float(std::max<size_t>(totalTris, 1));
const float f1 = 0.03f + 0.9f * float(trisDone + parts[i].T.size()) / float(std::max<size_t>(totalTris, 1));
trisDone += parts[i].T.size();
const std::function<bool(float)> pieceReport = [&](float f) { return report(f0 + (f1 - f0) * f); };
PieceResult r;
double want = budget[i];
bool doneByV2 = false;
if (opt.method == QRemeshMethod::V2) {
qr::FieldPieceResult fr;
bool cancelled = false;
const bool ok = qr::remeshPieceV2(parts[i], axis, want, opt, diag, guides, pieceReport, fr, cancelled);
if (cancelled) {
error = "Quad Remesh cancelled";
return false;
}
st.attempts += fr.attempts;
st.singularities += fr.singularities;
if (ok && !fr.mesh.quads.empty()) {
r.mesh = std::move(fr.mesh);
r.seam = std::move(fr.seam);
doneByV2 = true;
} else {
++st.fallbackPieces;
if (timing) std::fprintf(stderr, " piece %zu: Quad Remesh 2 fell back to legacy (%s)\n", i, fr.why.c_str());
}
}
// A piece the lattice misses is tried again finer, then kept as it is (its own triangles).
for (int attempt = 0; attempt < 3 && r.mesh.quads.empty(); ++attempt) {
r = PieceResult{};
want = budget[i] * std::pow(2.5, attempt);
if (!remeshPiece(parts[i], axis, want, opt, diag, guides, pieceReport, mark, r)) {
error = "Quad Remesh cancelled";
return false;
}
st.attempts += r.attempts;
}
// The lattice round a guide can go wrong by chance (where the field's singularities land, which the
// smallest rounding differences move): a broken loop or a fan by a guide is tried with other starts for
// the field, keeping the best.
for (uint32_t seed = 1; seed <= 2 && r.guideDefects > 0 && !r.mesh.quads.empty() && !doneByV2; ++seed) {
QRemeshOptions again = opt;
again.seed = opt.seed + seed * 7919u;
PieceResult other;
if (!remeshPiece(parts[i], axis, want, again, diag, guides, pieceReport, mark, other)) {
error = "Quad Remesh cancelled";
return false;
}
st.attempts += other.attempts;
if (!other.mesh.quads.empty() && other.guideDefects < r.guideDefects) r = std::move(other);
}
const uint32_t base = uint32_t(qm.P.size());
if (r.mesh.quads.empty()) {
const WorkMesh& p = parts[i];
qm.P.insert(qm.P.end(), p.P.begin(), p.P.end());
for (const glm::uvec3& t : p.T) qm.tris.push_back(t + glm::uvec3(base));
for (const vec3& v : p.P) seam.push_back(axis >= 0 && std::abs(v[axis]) <= 1e-6f * diag);
continue;
}
if (timing)
std::fprintf(stderr, " piece %zu: %zu triangles, area %.4g, budget %.0f -> %zu quads\n", i, parts[i].T.size(),
partArea[i], budget[i], r.mesh.quads.size());
qm.P.insert(qm.P.end(), r.mesh.P.begin(), r.mesh.P.end());
for (const glm::uvec4& q : r.mesh.quads) qm.quads.push_back(q + glm::uvec4(base));
for (const glm::uvec3& t : r.mesh.tris) qm.tris.push_back(t + glm::uvec3(base));
seam.insert(seam.end(), r.seam.begin(), r.seam.end());
}
parts.clear();
if (qm.quads.empty() && qm.tris.empty()) {
error = "Quad Remesh could not build quads on this surface (try a higher Target or turn Follow Face Groups off)";
return false;
}
if (!report(0.94f)) return false;
// Symmetry: mirror the half, welding the vertices on the plane.
if (axis >= 0) {
const size_t nv = qm.P.size(), nq = qm.quads.size(), nt = qm.tris.size();
std::vector<uint32_t> mirror(nv);
for (uint32_t v = 0; v < nv; ++v) {
if (seam[v]) {
qm.P[v][axis] = 0.0f;
mirror[v] = v;
} else {
mirror[v] = uint32_t(qm.P.size());
vec3 p = qm.P[v];
p[axis] = -p[axis];
qm.P.push_back(p);
}
}
for (size_t f = 0; f < nq; ++f) {
const glm::uvec4 q = qm.quads[f];
qm.quads.push_back({mirror[q.w], mirror[q.z], mirror[q.y], mirror[q.x]});
}
for (size_t f = 0; f < nt; ++f) {
const glm::uvec3 t = qm.tris[f];
qm.tris.push_back({mirror[t.z], mirror[t.y], mirror[t.x]});
}
for (vec3& p : qm.P) p[axis] += center;
// A model only nearly symmetric: the topology stays mirrored, each side sits on its own surface.
if (st.asymmetry > 1e-3f)
parallelFor(qm.P.size(), [&](size_t b, size_t e) {
for (size_t v = b; v < e; ++v) {
SurfaceHit hit;
if (full.closestPoint(qm.P[v], 0.25f * diag, hit)) qm.P[v] = hit.position;
}
});
}
// Output mesh: each quad as two triangles split along corner 0 - 2, then any pieces kept as triangles.
Mesh m;
m.positions = qm.P;
m.triangles.reserve(qm.quads.size() * 2 + qm.tris.size());
// Each quad split along a diagonal that isn't an edge of another face (else that edge would be used by four
// triangles), the shorter one when both are free.
std::unordered_map<uint64_t, uint8_t> quadEdges;
for (const auto& q : qm.quads)
for (int k = 0; k < 4; ++k) quadEdges[edgeKey(q[k], q[(k + 1) % 4])] = 1;
for (const glm::uvec3& t : qm.tris)
for (int k = 0; k < 3; ++k) quadEdges[edgeKey(t[k], t[(k + 1) % 3])] = 1;
for (const auto& q : qm.quads) {
const uint32_t t = uint32_t(m.triangles.size());
const bool xzTaken = quadEdges.count(edgeKey(q.x, q.z)) > 0, ywTaken = quadEdges.count(edgeKey(q.y, q.w)) > 0;
const bool useYW = (xzTaken && !ywTaken) ||
(xzTaken == ywTaken && glm::length(qm.P[q.y] - qm.P[q.w]) < 0.98f * glm::length(qm.P[q.x] - qm.P[q.z]));
if (useYW) {
m.triangles.push_back({q.y, q.z, q.w});
m.triangles.push_back({q.y, q.w, q.x});
quadEdges[edgeKey(q.y, q.w)] = 1; // two quads with the same diagonal would also share it four ways
} else {
m.triangles.push_back({q.x, q.y, q.z});
m.triangles.push_back({q.x, q.z, q.w});
quadEdges[edgeKey(q.x, q.z)] = 1;
}
m.pairQuad(t, t + 1);
}
for (const glm::uvec3& t : qm.tris) m.triangles.push_back(t);
if (!m.quadPartners.empty()) m.quadPartners.resize(m.triangles.size(), Mesh::kNoQuad); // the triangles after the quads
if (!report(0.96f)) return false;
// Attributes from the closest point of the original sculpt.
const bool needAttr = source.hasMask() || source.hasColors() || opt.keepGroups;
if (needAttr) {
buildFull();
const float reach = diag;
if (source.hasMask() || source.hasColors()) {
if (source.hasMask()) m.ensureMask();
if (source.hasColors()) m.ensureColors();
parallelFor(m.positions.size(), [&](size_t b, size_t e) {
for (size_t v = b; v < e; ++v) {
SurfaceHit hit;
if (!full.closestPoint(m.positions[v], reach, hit)) continue;
const glm::uvec3 t = source.triangles[hit.prim];
if (source.hasMask())
m.mask[v] = hit.bary.x * source.mask[t.x] + hit.bary.y * source.mask[t.y] + hit.bary.z * source.mask[t.z];
if (source.hasColors())
m.colors[v] = hit.bary.x * source.colors[t.x] + hit.bary.y * source.colors[t.y] +
hit.bary.z * source.colors[t.z];
}
});
}
if (opt.keepGroups && source.hasFaceGroups()) {
m.ensureFaceGroups();
const size_t nq = qm.quads.size();
parallelFor(nq, [&](size_t b, size_t e) {
for (size_t q = b; q < e; ++q) {
const glm::uvec3 t0 = m.triangles[2 * q], t1 = m.triangles[2 * q + 1];
const vec3 c = 0.25f * (m.positions[t0.x] + m.positions[t0.y] + m.positions[t0.z] + m.positions[t1.z]);
SurfaceHit hit;
const uint32_t g = full.closestPoint(c, reach, hit) ? source.facegroupAt(hit.prim) : 0u;
m.facegroups[2 * q] = m.facegroups[2 * q + 1] = g;
}
});
for (size_t t = 2 * nq; t < m.triangles.size(); ++t) {
const glm::uvec3 tri = m.triangles[t];
SurfaceHit hit;
const vec3 c = (m.positions[tri.x] + m.positions[tri.y] + m.positions[tri.z]) / 3.0f;
m.facegroups[t] = full.closestPoint(c, reach, hit) ? source.facegroupAt(hit.prim) : 0u;
}
}
}
m.rebuildTopology();
m.recomputeAllNormals();
const TopologyReport topo = topologyReport(m);
st.quads = topo.quads;
st.triangles = topo.triangles;
st.boundaryEdges = topo.boundaryEdges;
st.nonManifoldEdges = topo.nonManifoldEdges;
{
double len = 0.0;
size_t cnt = 0;
for (const auto& q : qm.quads)
for (int k = 0; k < 4; ++k) len += glm::length(qm.P[q[k]] - qm.P[q[(k + 1) % 4]]), ++cnt;
st.edgeLength = cnt ? float(len / double(cnt)) : 0.0f;
}
st.method = opt.method;
st.seconds = std::chrono::duration<double>(std::chrono::steady_clock::now() - start).count();
if (opt.measureQuality) st.quality = quadQuality(m, &source);
if (stats) *stats = st;
out = std::move(m);
return report(1.0f);
}
TopologyReport topologyReport(const Mesh& mesh) {
TopologyReport r;
// Faces as exported: quads once, triangles.
std::vector<std::vector<uint32_t>> faces;
for (uint32_t t = 0; t < mesh.triangleCount(); ++t) {
glm::uvec4 f;
const int n = mesh.exportFace(t, f);
if (n == 0) continue;
faces.push_back(n == 4 ? std::vector<uint32_t>{f.x, f.y, f.z, f.w} : std::vector<uint32_t>{f.x, f.y, f.z});
++(n == 4 ? r.quads : r.triangles);
}
r.faces = faces.size();
// Directed edge counts.
std::unordered_map<uint64_t, std::pair<int, int>> edges; // key (min,max) -> (uses a->b with a<b, uses b->a)
for (const auto& f : faces)
for (size_t k = 0; k < f.size(); ++k) {
const uint32_t a = f[k], b = f[(k + 1) % f.size()];
auto& e = edges[edgeKey(a, b)];
++(a < b ? e.first : e.second);
}
std::vector<std::vector<std::pair<uint32_t, uint32_t>>> fan(mesh.vertexCount()); // per vertex: (prev, next) corners
for (const auto& f : faces)
for (size_t k = 0; k < f.size(); ++k)
fan[f[k]].push_back({f[(k + f.size() - 1) % f.size()], f[(k + 1) % f.size()]});
for (auto& [key, e] : edges) {
const int total = e.first + e.second;
if (total == 1) ++r.boundaryEdges;
else if (total > 2 || e.first != 1 || e.second != 1) ++r.nonManifoldEdges;
}
// A manifold vertex's corners chain into one fan (a cycle inside, a path on a boundary).
for (uint32_t v = 0; v < fan.size(); ++v) {
const auto& c = fan[v];
if (c.size() < 2) continue;
std::unordered_map<uint32_t, size_t> byNext; // corner whose "next" is u
for (size_t i = 0; i < c.size(); ++i) byNext[c[i].second] = i;
std::vector<uint8_t> seen(c.size(), 0);
size_t start = 0;
// Start from a corner whose prev neighbour isn't any corner's next (a boundary end), if any.
for (size_t i = 0; i < c.size(); ++i) {
bool hasPrev = false;
for (size_t j = 0; j < c.size(); ++j) hasPrev |= c[j].first == c[i].second;
if (!hasPrev) start = i;
}
size_t walked = 0, cur = start;
while (!seen[cur]) {
seen[cur] = 1;
++walked;
// The corner across the edge (v, c[cur].first): it has that vertex as its "next".
auto it = byNext.find(c[cur].first);
if (it == byNext.end()) break;
cur = it->second;
}
if (walked != c.size()) ++r.nonManifoldVertices;
}
return r;
}
} // namespace sf