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 2: the integer-grid map. A seamless parametrization whose gradients follow the cross field at the wanted
// quad size, with transitions across the cut that are grid symmetries (quarter turns plus integer shifts),
// singularities on lattice points and feature lines on lattice lines, so the integer lattice drawn on the surface is
// a quad mesh with poles only at the field's singularities. After Mixed-Integer Quadrangulation (Bommes, Zimmer &
// Kobbelt, SIGGRAPH 2009) and integer-grid maps (Bommes, Campen, Ebke, Alliez & Kobbelt, SIGGRAPH 2013); the
// constraint elimination and greedy rounding are our own small solver (no CoMISo).
//
// 1. Comb the field along a spanning tree of the triangles; the edges off the tree, pruned to the branches that
// reach singularities, open edges or handles, are the cut.
// 2. Unknowns (u, v) per vertex wedge (corners not separated by the cut); linear constraints: across each cut edge
// the two sides differ by the quarter turn and an integer shift, feature edges keep one coordinate on an
// integer, singularities sit on integers. Eliminated one by one (integer unknowns stay integer combinations).
// 3. Least squares for the gradients, solved by conjugate gradients; integer unknowns rounded nearest-first in
// batches, each followed by a warm-started re-solve.
#include "core/QRemesh2.h"
#include "core/QRemesh2Solver.h"
#include "core/ThreadPool.h"
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <numbers>
#include <numeric>
#include <queue>
namespace sf::qr2 {
namespace {
constexpr double kPi = std::numbers::pi;
struct Term {
uint32_t var;
double a;
};
// Linear constraints sum a_i x_i + c = 0, eliminated as they come: each picks one unknown (the pivot) and expresses it
// by the others; expressions only ever mention unknowns still free.
class Eliminator {
public:
// kind: 0 = real, 1..3 = integer (1 eliminated first: seam shifts, 2: feature lines, 3: singularity positions).
uint32_t add(uint8_t kind) {
kind_.push_back(kind);
elim_.push_back(0);
expr_.emplace_back();
cst_.push_back(0.0);
users_.emplace_back();
return uint32_t(kind_.size() - 1);
}
size_t size() const { return kind_.size(); }
bool eliminated(uint32_t v) const { return elim_[v] != 0; }
uint8_t kind(uint32_t v) const { return kind_[v]; }
const std::vector<Term>& expr(uint32_t v) const { return expr_[v]; }
double constant(uint32_t v) const { return cst_[v]; }
size_t lostIntegers() const { return lost_; }
void constrain(const std::vector<Term>& row, double c) {
// Substitute.
std::vector<Term> r;
double k = c;
for (const Term& t : row) {
if (std::abs(t.a) < 1e-14) continue;
if (elim_[t.var]) {
for (const Term& u : expr_[t.var]) r.push_back({u.var, t.a * u.a});
k += t.a * cst_[t.var];
} else {
r.push_back(t);
}
}
std::sort(r.begin(), r.end(), [](const Term& x, const Term& y) { return x.var < y.var; });
std::vector<Term> m;
for (const Term& t : r) {
if (!m.empty() && m.back().var == t.var) m.back().a += t.a;
else m.push_back(t);
}
m.erase(std::remove_if(m.begin(), m.end(), [](const Term& t) { return std::abs(t.a) < 1e-9; }), m.end());
if (m.empty()) return; // redundant (or inconsistent, which the least squares then can't satisfy)
// An all-integer row with integer coefficients: divide by their common factor (a parity row such as
// 2a - 2b + 2c = 0 then keeps a pivot with coefficient 1, so integers stay integer).
{
bool allInt = std::abs(k - std::round(k)) < 1e-9;
long g = 0;
for (const Term& t : m) {
if (kind_[t.var] == 0 || std::abs(t.a - std::round(t.a)) > 1e-9) allInt = false;
else g = std::gcd(g, std::labs(std::lround(t.a)));
}
if (allInt && g > 1 && std::abs(k / double(g) - std::round(k / double(g))) < 1e-9) {
for (Term& t : m) t.a /= double(g);
k /= double(g);
}
}
// Pivot: a real unknown with the largest coefficient; else an integer one with coefficient +-1, lowest kind.
int best = -1;
for (size_t i = 0; i < m.size(); ++i)
if (kind_[m[i].var] == 0 && (best < 0 || std::abs(m[i].a) > std::abs(m[size_t(best)].a) + 1e-12)) best = int(i);
if (best < 0)
for (size_t i = 0; i < m.size(); ++i)
if (std::abs(std::abs(m[i].a) - 1.0) < 1e-9 &&
(best < 0 || kind_[m[i].var] < kind_[m[size_t(best)].var]))
best = int(i);
if (best < 0) {
++lost_;
if (std::getenv("SF_QR2_LOST")) {
std::fprintf(stderr, " lost integer:");
for (const Term& t : m) std::fprintf(stderr, " %g*[k%d]", t.a, kind_[t.var]);
std::fprintf(stderr, " + %g\n", k);
}
for (size_t i = 0; i < m.size(); ++i)
if (best < 0 || std::abs(m[i].a) > std::abs(m[size_t(best)].a)) best = int(i);
}
const uint32_t p = m[size_t(best)].var;
const double ap = m[size_t(best)].a;
std::vector<Term> e;
for (const Term& t : m)
if (t.var != p) e.push_back({t.var, -t.a / ap});
const double ec = -k / ap;
// Replace p in every expression using it.
for (uint32_t q : users_[p]) {
if (!elim_[q]) continue;
auto& ex = expr_[q];
double ap2 = 0.0;
for (const Term& t : ex)
if (t.var == p) ap2 += t.a;
if (ap2 == 0.0) continue;
std::vector<Term> merged;
merged.reserve(ex.size() + e.size());
for (const Term& t : ex)
if (t.var != p) merged.push_back(t);
for (const Term& t : e) merged.push_back({t.var, ap2 * t.a});
std::sort(merged.begin(), merged.end(), [](const Term& x, const Term& y) { return x.var < y.var; });
ex.clear();
for (const Term& t : merged) {
if (!ex.empty() && ex.back().var == t.var) ex.back().a += t.a;
else ex.push_back(t);
}
ex.erase(std::remove_if(ex.begin(), ex.end(), [](const Term& t) { return std::abs(t.a) < 1e-12; }), ex.end());
cst_[q] += ap2 * ec;
for (const Term& t : e) addUser(t.var, q);
}
users_[p].clear();
users_[p].shrink_to_fit();
elim_[p] = 1;
expr_[p] = e;
cst_[p] = ec;
for (const Term& t : e) addUser(t.var, p);
}
private:
void addUser(uint32_t var, uint32_t q) {
auto& u = users_[var];
if (!u.empty() && u.back() == q) return;
u.push_back(q);
if (u.size() >= 32 && (u.size() & (u.size() - 1)) == 0) { // at powers of two: drop duplicates and stale ones
std::sort(u.begin(), u.end());
u.erase(std::unique(u.begin(), u.end()), u.end());
u.erase(std::remove_if(u.begin(), u.end(), [&](uint32_t x) {
if (!elim_[x]) return true;
for (const Term& t : expr_[x])
if (t.var == var) return false;
return true;
}), u.end());
}
}
std::vector<uint8_t> kind_, elim_;
std::vector<std::vector<Term>> expr_;
std::vector<double> cst_;
std::vector<std::vector<uint32_t>> users_;
size_t lost_ = 0;
};
template <class F>
double blockSum(size_t n, F&& term) {
const size_t block = 8192, blocks = (n + block - 1) / block;
std::vector<double> part(blocks, 0.0);
poolFor(n, [&](size_t b, size_t e) {
double s = 0.0;
for (size_t i = b; i < e; ++i) s += term(i);
part[b / block] = s;
}, block);
double s = 0.0;
for (double p : part) s += p;
return s;
}
struct Csr {
std::vector<uint32_t> off, col;
std::vector<double> val;
std::vector<double> diag;
size_t n = 0;
};
struct ReducedOp {
std::function<void(const std::vector<double>&, std::vector<double>&)> apply;
const std::vector<double>* diag;
size_t n;
};
// Conjugate gradients on the unknowns not fixed (Jacobi preconditioner); fixed entries of x stay. Returns iterations.
int conjugateGradients(const ReducedOp& A, const std::vector<double>& b, const std::vector<uint8_t>& fixed,
std::vector<double>& x, double tol, int maxIt, const std::function<bool()>& cancelled, bool& stop,
const std::function<void(const std::vector<double>&, std::vector<double>&)>& pre = {}) {
const size_t n = A.n;
const std::vector<double>& D = *A.diag;
std::vector<double> r(n), z(n), d(n), q(n);
auto precond = [&] {
if (pre) {
pre(r, z);
for (size_t i = 0; i < n; ++i)
if (fixed[i]) z[i] = 0.0;
} else {
for (size_t i = 0; i < n; ++i) z[i] = fixed[i] ? 0.0 : r[i] / D[i];
}
};
A.apply(x, q);
for (size_t i = 0; i < n; ++i) r[i] = fixed[i] ? 0.0 : b[i] - q[i];
precond();
d = z;
double rz = blockSum(n, [&](size_t i) { return r[i] * z[i]; });
const double bn = std::sqrt(blockSum(n, [&](size_t i) { return fixed[i] ? 0.0 : b[i] * b[i]; })) + 1e-30;
int it = 0;
for (; it < maxIt; ++it) {
const double rn = std::sqrt(blockSum(n, [&](size_t i) { return r[i] * r[i]; }));
if (rn < tol * bn) break;
if ((it & 31) == 0 && cancelled && cancelled()) {
stop = true;
return it;
}
A.apply(d, q);
const double dq = blockSum(n, [&](size_t i) { return fixed[i] ? 0.0 : d[i] * q[i]; });
if (!(dq > 1e-300)) break;
const double alpha = rz / dq;
poolFor(n, [&](size_t b0, size_t e0) {
for (size_t i = b0; i < e0; ++i) {
if (fixed[i]) continue;
x[i] += alpha * d[i];
r[i] -= alpha * q[i];
}
});
precond();
const double rzNew = blockSum(n, [&](size_t i) { return r[i] * z[i]; });
const double beta = rzNew / rz;
rz = rzNew;
poolFor(n, [&](size_t b0, size_t e0) {
for (size_t i = b0; i < e0; ++i) d[i] = fixed[i] ? 0.0 : z[i] + beta * d[i];
});
}
return it;
}
} // namespace
bool solveGridMap(const Proxy& p, const Frames& f, CrossField& field, GridMap& out, const std::function<bool()>& cancelled) {
static const bool timing = std::getenv("SF_QREMESH_TIMING") != nullptr;
const size_t nt = p.T.size(), nv = p.P.size();
const size_t nc = 3 * nt;
if (nt == 0) return false;
// 1. Comb along a breadth-first spanning tree of the triangles.
std::vector<uint8_t> tree(nc, 0), seen(nt, 0);
{
std::vector<uint32_t> queue;
queue.reserve(nt);
for (uint32_t root = 0; root < nt; ++root) {
if (seen[root]) continue;
seen[root] = 1;
queue.clear();
queue.push_back(root);
for (size_t qi = 0; qi < queue.size(); ++qi) {
const uint32_t t = queue[qi];
for (int k = 0; k < 3; ++k) {
const uint32_t c = 3 * t + uint32_t(k), o = p.opp[c];
if (o == kNone || seen[o / 3]) continue;
const uint32_t g = o / 3;
seen[g] = 1;
// Turn g's cross so it matches t's across this edge.
field.theta[g] -= float(field.match[c]) * float(kPi / 2.0);
// match from t to g is now 0; refresh g's other corners lazily below.
tree[c] = tree[o] = 1;
// Update matchings of g's edges for the turn (q - m on corners of g, + m on their twins).
const int m = field.match[c];
for (int j = 0; j < 3; ++j) {
const uint32_t cg = 3 * g + uint32_t(j), og = p.opp[cg];
field.match[cg] = int8_t((field.match[cg] + m) % 4);
if (og != kNone) field.match[og] = int8_t((field.match[og] + 4 - m) % 4);
}
queue.push_back(g);
}
}
}
}
// Sanity: tree edges have match 0.
// 2. Cut graph: interior edges off the tree, pruned.
std::vector<uint8_t> cut(nc, 0), open(nv, 0);
for (uint32_t c = 0; c < nc; ++c) {
if (p.opp[c] == kNone) {
open[p.T[c / 3][c % 3]] = open[p.T[c / 3][(c % 3 + 1) % 3]] = 1;
continue;
}
if (!tree[c]) cut[c] = 1;
}
{
std::vector<std::vector<uint32_t>> vedges(nv); // per vertex: cut edges as their lower corner
for (uint32_t c = 0; c < nc; ++c) {
if (!cut[c] || p.opp[c] < c) continue;
vedges[p.T[c / 3][c % 3]].push_back(c);
vedges[p.T[c / 3][(c % 3 + 1) % 3]].push_back(c);
}
std::vector<int> deg(nv, 0);
for (uint32_t v = 0; v < nv; ++v) deg[v] = int(vedges[v].size());
std::vector<uint32_t> stack;
for (uint32_t v = 0; v < nv; ++v)
if (deg[v] == 1 && !open[v] && field.vertexIndex[v] == 0) stack.push_back(v);
while (!stack.empty()) {
const uint32_t v = stack.back();
stack.pop_back();
if (deg[v] != 1) continue;
uint32_t e = kNone;
for (uint32_t c : vedges[v])
if (cut[c]) e = c;
if (e == kNone) continue;
cut[e] = cut[p.opp[e]] = 0;
const uint32_t a = p.T[e / 3][e % 3], b = p.T[e / 3][(e % 3 + 1) % 3];
--deg[a], --deg[b];
const uint32_t other = a == v ? b : a;
if (deg[other] == 1 && !open[other] && field.vertexIndex[other] == 0) stack.push_back(other);
}
}
size_t cutEdges = 0;
for (uint32_t c = 0; c < nc; ++c) cutEdges += cut[c] && p.opp[c] > c;
// 3. Wedges: corners of a vertex joined across edges that are neither open nor cut.
std::vector<uint32_t> parent(nc);
std::iota(parent.begin(), parent.end(), 0u);
auto find = [&](uint32_t x) {
while (parent[x] != x) x = parent[x] = parent[parent[x]];
return x;
};
auto cornerOf = [&](uint32_t t, uint32_t v) -> uint32_t {
for (int k = 0; k < 3; ++k)
if (p.T[t][k] == v) return 3 * t + uint32_t(k);
return kNone;
};
for (uint32_t c = 0; c < nc; ++c) {
const uint32_t o = p.opp[c];
if (o == kNone || cut[c] || o < c) continue;
const uint32_t t = c / 3, g = o / 3;
const uint32_t a = p.T[t][c % 3], b = p.T[t][(c % 3 + 1) % 3];
for (uint32_t v : {a, b}) {
const uint32_t x = find(cornerOf(t, v)), y = find(cornerOf(g, v));
if (x != y) parent[std::max(x, y)] = std::min(x, y);
}
}
std::vector<uint32_t> copyOf(nc), copyId(nc, kNone);
uint32_t copies = 0;
for (uint32_t c = 0; c < nc; ++c) {
const uint32_t r = find(c);
if (copyId[r] == kNone) copyId[r] = copies++;
copyOf[c] = copyId[r];
}
Eliminator el;
for (uint32_t i = 0; i < 2 * copies; ++i) el.add(0);
auto U = [&](uint32_t corner) { return 2 * copyOf[corner]; };
// Axis of each triangle's field: X = (cos theta, sin theta) in its frame.
auto axisOfEdge = [&](uint32_t t, const vec3& e) { // 0: the edge runs along u (so v is constant), 1: along v
const double th = double(field.theta[t]);
const double x = double(glm::dot(e, f.e1[t])), y = double(glm::dot(e, f.e2[t]));
const double du = std::abs(x * std::cos(th) + y * std::sin(th)), dv = std::abs(-x * std::sin(th) + y * std::cos(th));
return du >= dv ? 0 : 1;
};
// Singularities on lattice points.
size_t ints = 0;
{
std::vector<uint8_t> done(nv, 0);
for (uint32_t c = 0; c < nc; ++c) {
const uint32_t v = p.T[c / 3][c % 3];
if (field.vertexIndex[v] == 0 || open[v] || done[v]) continue;
done[v] = 1;
const uint32_t iu = el.add(3), iv = el.add(3);
ints += 2;
el.constrain({{U(c), 1.0}, {iu, -1.0}}, 0.0);
el.constrain({{U(c) + 1, 1.0}, {iv, -1.0}}, 0.0);
}
}
// Feature lines on lattice lines.
for (uint32_t c = 0; c < nc; ++c) {
if (!p.feature[c]) continue;
const uint32_t t = c / 3, k = c % 3;
const vec3 e = p.P[p.T[t][(k + 1) % 3]] - p.P[p.T[t][k]];
const int along = axisOfEdge(t, e);
const uint32_t coord = along == 0 ? 1 : 0; // the coordinate that stays constant
const uint32_t s = el.add(2);
++ints;
el.constrain({{U(c) + coord, 1.0}, {s, -1.0}}, 0.0);
el.constrain({{U(3 * t + (k + 1) % 3) + coord, 1.0}, {s, -1.0}}, 0.0);
}
// Seams: across each cut edge, (u, v) on the far side = R^m (u, v) + integer shift.
for (uint32_t c = 0; c < nc; ++c) {
if (!cut[c] || p.opp[c] < c) continue;
const uint32_t o = p.opp[c], t = c / 3, g = o / 3, k = c % 3;
const int m = field.match[c];
const uint32_t tu = el.add(1), tv = el.add(1);
ints += 2;
for (uint32_t v : {p.T[t][k], p.T[t][(k + 1) % 3]}) {
const uint32_t a = U(cornerOf(t, v)), b = U(cornerOf(g, v));
// R^m: m=1: (u, v) -> (v, -u).
double r[2][2];
switch (m) {
case 0: r[0][0] = 1, r[0][1] = 0, r[1][0] = 0, r[1][1] = 1; break;
case 1: r[0][0] = 0, r[0][1] = 1, r[1][0] = -1, r[1][1] = 0; break;
case 2: r[0][0] = -1, r[0][1] = 0, r[1][0] = 0, r[1][1] = -1; break;
default: r[0][0] = 0, r[0][1] = -1, r[1][0] = 1, r[1][1] = 0; break;
}
el.constrain({{b, 1.0}, {a, -r[0][0]}, {a + 1, -r[0][1]}, {tu, -1.0}}, 0.0);
el.constrain({{b + 1, 1.0}, {a, -r[1][0]}, {a + 1, -r[1][1]}, {tv, -1.0}}, 0.0);
}
}
if (timing)
std::fprintf(stderr, " grid map: %zu triangles, %u wedges, %zu cut edges, %zu integer unknowns (%zu lost)\n", nt,
copies, cutEdges, ints, el.lostIntegers());
if (timing) {
size_t maxLen = 0, total = 0;
for (uint32_t v = 0; v < el.size(); ++v)
if (el.eliminated(v)) maxLen = std::max(maxLen, el.expr(v).size()), total += el.expr(v).size();
std::fprintf(stderr, " grid map: expressions max %zu terms, %zu in all\n", maxLen, total);
}
// 4. Free unknowns. The reduced system C^T K C y = C^T (b - K d) (x = C y + d) is applied without forming it:
// the cut tree makes C fill in (a transition is the composition of everything below it), C^T K C would not fit.
const size_t nvar = el.size(), ncopy = 2 * size_t(copies);
std::vector<uint32_t> freeId(nvar, kNone);
std::vector<uint32_t> freeVars;
for (uint32_t v = 0; v < nvar; ++v)
if (!el.eliminated(v)) {
freeId[v] = uint32_t(freeVars.size());
freeVars.push_back(v);
}
const size_t nf = freeVars.size();
auto expand = [&](uint32_t v, std::vector<Term>& terms, double& c) {
terms.clear();
if (!el.eliminated(v)) {
terms.push_back({freeId[v], 1.0});
c = 0.0;
return;
}
for (const Term& t : el.expr(v)) terms.push_back({freeId[t.var], t.a});
c = el.constant(v);
};
// K and b on the wedge unknowns: per triangle, the hat-function gradients against the target gradients.
Csr K;
K.n = ncopy;
std::vector<double> bFull(ncopy, 0.0);
{
struct Trip {
uint32_t r, c;
double v;
};
std::vector<Trip> trips;
trips.reserve(nt * 18);
for (uint32_t t = 0; t < nt; ++t) {
const glm::uvec3 tri = p.T[t];
const vec3 o = p.P[tri.x];
vec2 q[3];
for (int k = 0; k < 3; ++k) {
const vec3 d = p.P[tri[k]] - o;
q[k] = {glm::dot(d, f.e1[t]), glm::dot(d, f.e2[t])};
}
const double A2 = double(q[1].x - q[0].x) * double(q[2].y - q[0].y) - double(q[2].x - q[0].x) * double(q[1].y - q[0].y);
if (!(A2 > 1e-30)) continue;
const double A = 0.5 * A2;
double gx[3], gy[3];
for (int k = 0; k < 3; ++k) {
const vec2 e = q[(k + 2) % 3] - q[(k + 1) % 3];
gx[k] = -double(e.y) / A2;
gy[k] = double(e.x) / A2;
}
const double h = (double(p.size[tri.x]) + double(p.size[tri.y]) + double(p.size[tri.z])) / 3.0;
const double th = double(field.theta[t]);
const double gu[2] = {std::cos(th) / h, std::sin(th) / h}, gv[2] = {-std::sin(th) / h, std::cos(th) / h};
for (int coord = 0; coord < 2; ++coord) {
const double* g = coord == 0 ? gu : gv;
for (int i = 0; i < 3; ++i) {
const uint32_t vi = U(3 * t + uint32_t(i)) + uint32_t(coord);
bFull[vi] += A * (gx[i] * g[0] + gy[i] * g[1]);
for (int j = 0; j < 3; ++j) {
const uint32_t vj = U(3 * t + uint32_t(j)) + uint32_t(coord);
trips.push_back({vi, vj, A * (gx[i] * gx[j] + gy[i] * gy[j])});
}
}
}
}
std::sort(trips.begin(), trips.end(), [](const Trip& x, const Trip& y) { return x.r < y.r || (x.r == y.r && x.c < y.c); });
K.off.assign(ncopy + 1, 0);
for (size_t i = 0; i < trips.size();) {
size_t j = i;
double v = 0.0;
while (j < trips.size() && trips[j].r == trips[i].r && trips[j].c == trips[i].c) v += trips[j++].v;
K.col.push_back(trips[i].c);
K.val.push_back(v);
++K.off[trips[i].r + 1];
i = j;
}
for (size_t i = 0; i < ncopy; ++i) K.off[i + 1] += K.off[i];
K.diag.assign(ncopy, 0.0);
for (size_t i = 0; i < ncopy; ++i)
for (uint32_t k = K.off[i]; k < K.off[i + 1]; ++k)
if (K.col[k] == i) K.diag[i] = K.val[k];
}
// C as rows (per wedge unknown) and columns (per free unknown).
std::vector<uint32_t> cOff(ncopy + 1, 0), cCol;
std::vector<double> cVal, dConst(ncopy, 0.0);
{
std::vector<Term> terms;
for (uint32_t v = 0; v < ncopy; ++v) {
double c;
expand(v, terms, c);
dConst[v] = c;
for (const Term& t : terms) cCol.push_back(t.var), cVal.push_back(t.a);
cOff[v + 1] = uint32_t(cCol.size());
}
}
std::vector<uint32_t> tOff(nf + 1, 0), tRow(cCol.size());
std::vector<double> tVal(cCol.size());
for (uint32_t c : cCol) ++tOff[c + 1];
for (size_t i = 0; i < nf; ++i) tOff[i + 1] += tOff[i];
{
std::vector<uint32_t> fill(tOff.begin(), tOff.end() - 1);
for (uint32_t v = 0; v < ncopy; ++v)
for (uint32_t k = cOff[v]; k < cOff[v + 1]; ++k) {
const uint32_t at = fill[cCol[k]]++;
tRow[at] = v;
tVal[at] = cVal[k];
}
}
if (timing) std::fprintf(stderr, " grid map: C has %zu terms\n", cCol.size());
auto mulK = [&](const std::vector<double>& x, std::vector<double>& z) {
poolFor(ncopy, [&](size_t b0, size_t e0) {
for (size_t i = b0; i < e0; ++i) {
double s = 0.0;
for (uint32_t k = K.off[i]; k < K.off[i + 1]; ++k) s += K.val[k] * x[K.col[k]];
z[i] = s;
}
});
};
std::vector<double> rhs(nf, 0.0), diag(nf, 0.0);
{
std::vector<double> kd(ncopy);
mulK(dConst, kd);
for (size_t j = 0; j < nf; ++j) {
double s = 0.0, dg = 0.0;
for (uint32_t k = tOff[j]; k < tOff[j + 1]; ++k) {
s += tVal[k] * (bFull[tRow[k]] - kd[tRow[k]]);
dg += tVal[k] * tVal[k] * K.diag[tRow[k]];
}
rhs[j] = s;
diag[j] = dg;
}
}
double meanDiag = 0.0;
for (double d : diag) meanDiag += d;
meanDiag = nf ? meanDiag / double(nf) : 1.0;
const double reg = 1e-7 * meanDiag;
for (double& d : diag) d = d > 0.0 ? d + reg : 1.0;
std::vector<double> xs(ncopy), zs(ncopy);
const ReducedOp op{[&](const std::vector<double>& yv, std::vector<double>& outv) {
poolFor(ncopy, [&](size_t b0, size_t e0) {
for (size_t v = b0; v < e0; ++v) {
double s = 0.0;
for (uint32_t k = cOff[v]; k < cOff[v + 1]; ++k) s += cVal[k] * yv[cCol[k]];
xs[v] = s;
}
});
mulK(xs, zs);
poolFor(nf, [&](size_t b0, size_t e0) {
for (size_t j = b0; j < e0; ++j) {
double s = reg * yv[j];
for (uint32_t k = tOff[j]; k < tOff[j + 1]; ++k) s += tVal[k] * zs[tRow[k]];
outv[j] = s;
}
});
}, &diag, nf};
// Multigrid preconditioner on a sparse stand-in for C^T K C: each wedge unknown mapped to its main free real
// unknown only (the integer fill-in dropped), integer unknowns on their own diagonal.
Multigrid<double> mg;
{
std::vector<int64_t> mainOf(ncopy, -1);
std::vector<double> mainCoef(ncopy, 0.0);
for (uint32_t v = 0; v < ncopy; ++v) {
double best = 0.0;
for (uint32_t k = cOff[v]; k < cOff[v + 1]; ++k)
if (el.kind(freeVars[cCol[k]]) == 0 && std::abs(cVal[k]) > best) best = std::abs(cVal[k]), mainOf[v] = cCol[k], mainCoef[v] = cVal[k];
}
std::vector<std::pair<uint64_t, double>> trips;
trips.reserve(K.val.size() + nf);
for (uint32_t i = 0; i < ncopy; ++i) {
if (mainOf[i] < 0) continue;
for (uint32_t k = K.off[i]; k < K.off[i + 1]; ++k) {
const uint32_t j = K.col[k];
if (mainOf[j] < 0) continue;
trips.push_back({(uint64_t(mainOf[i]) << 32) | uint64_t(mainOf[j]), mainCoef[i] * K.val[k] * mainCoef[j]});
}
}
for (size_t j = 0; j < nf; ++j) trips.push_back({(uint64_t(j) << 32) | j, el.kind(freeVars[j]) != 0 ? diag[j] : reg});
SparseMatrix<double> As;
As.build(nf, trips);
mg.build(As);
}
// The integer unknowns (singularity positions, seam shifts, feature lines) couple across the whole cut tree, which
// the stand-in leaves out: they get an exact dense block A_ii = S^T K S (S: their columns of C), and the
// preconditioner is a symmetric block Gauss-Seidel over (integers, reals, integers).
std::vector<uint32_t> intIdx(nf, kNone), intVars;
for (size_t j = 0; j < nf; ++j)
if (el.kind(freeVars[j]) != 0) intIdx[j] = uint32_t(intVars.size()), intVars.push_back(uint32_t(j));
const size_t mi = intVars.size();
std::vector<double> Aii(mi * mi, 0.0);
if (mi > 0 && mi <= 4000) {
// S rows (per wedge unknown: its integer terms) and W = K S.
std::vector<std::vector<std::pair<uint32_t, double>>> S(ncopy);
for (uint32_t v = 0; v < ncopy; ++v)
for (uint32_t k = cOff[v]; k < cOff[v + 1]; ++k)
if (intIdx[cCol[k]] != kNone) S[v].push_back({intIdx[cCol[k]], cVal[k]});
std::vector<double> acc(mi, 0.0);
std::vector<uint32_t> touched;
for (uint32_t v = 0; v < ncopy; ++v) {
if (S[v].empty()) continue;
// Row v of K S, then A_ii += S_v^T (K S)_v ... K is symmetric, so use (K S)_v = sum_u K_vu S_u.
touched.clear();
for (uint32_t k = K.off[v]; k < K.off[v + 1]; ++k)
for (const auto& [j, c] : S[K.col[k]]) {
if (acc[j] == 0.0) touched.push_back(j);
acc[j] += K.val[k] * c;
if (acc[j] == 0.0) acc[j] = 1e-300;
}
for (const auto& [i, c] : S[v])
for (uint32_t j : touched) Aii[size_t(i) * mi + j] += c * acc[j];
for (uint32_t j : touched) acc[j] = 0.0;
}
for (size_t i = 0; i < mi; ++i) Aii[i * mi + i] += reg;
}
std::vector<double> Lii; // Cholesky of A_ii over the integers not fixed yet
std::vector<uint32_t> liveInts;
auto factorInts = [&](const std::vector<uint8_t>& fixedMask) {
liveInts.clear();
for (size_t a = 0; a < mi; ++a)
if (!fixedMask[intVars[a]]) liveInts.push_back(uint32_t(a));
const size_t m = liveInts.size();
Lii.assign(m * m, 0.0);
for (size_t a = 0; a < m; ++a)
for (size_t b = 0; b < m; ++b) Lii[a * m + b] = Aii[size_t(liveInts[a]) * mi + liveInts[b]];
for (size_t j = 0; j < m; ++j) {
double d = Lii[j * m + j];
for (size_t k = 0; k < j; ++k) d -= Lii[j * m + k] * Lii[j * m + k];
d = std::sqrt(std::max(d, 1e-300));
Lii[j * m + j] = d;
for (size_t i = j + 1; i < m; ++i) {
double s2 = Lii[i * m + j];
for (size_t k = 0; k < j; ++k) s2 -= Lii[i * m + k] * Lii[j * m + k];
Lii[i * m + j] = s2 / d;
}
}
};
auto solveInts = [&](std::vector<double>& rhsI) { // in place, over liveInts
const size_t m = liveInts.size();
for (size_t i = 0; i < m; ++i) {
double s2 = rhsI[i];
for (size_t k = 0; k < i; ++k) s2 -= Lii[i * m + k] * rhsI[k];
rhsI[i] = s2 / Lii[i * m + i];
}
for (size_t i = m; i-- > 0;) {
double s2 = rhsI[i];
for (size_t k = i + 1; k < m; ++k) s2 -= Lii[k * m + i] * rhsI[k];
rhsI[i] = s2 / Lii[i * m + i];
}
};
const bool useIntBlock = mi > 0 && mi <= 4000;
std::vector<double> pt(nf), pz(nf), pr(nf), ri;
const std::function<void(const std::vector<double>&, std::vector<double>&)> precond =
[&](const std::vector<double>& r, std::vector<double>& z) {
if (!useIntBlock || liveInts.empty()) {
mg.apply(r, z);
return;
}
const size_t m = liveInts.size();
// z_i1 = A_ii^-1 r_i
ri.assign(m, 0.0);
for (size_t a = 0; a < m; ++a) ri[a] = r[intVars[liveInts[a]]];
solveInts(ri);
std::fill(pz.begin(), pz.end(), 0.0);
for (size_t a = 0; a < m; ++a) pz[intVars[liveInts[a]]] = ri[a];
// z_r = MG(r_r - A_ri z_i1)
op.apply(pz, pt);
for (size_t j = 0; j < nf; ++j) pr[j] = intIdx[j] == kNone ? r[j] - pt[j] : 0.0;
mg.apply(pr, z);
for (size_t j = 0; j < nf; ++j)
if (intIdx[j] != kNone) z[j] = 0.0;
// z_i = A_ii^-1 (r_i - A_ir z_r)
op.apply(z, pt);
for (size_t a = 0; a < m; ++a) ri[a] = r[intVars[liveInts[a]]] - pt[intVars[liveInts[a]]];
solveInts(ri);
for (size_t a = 0; a < m; ++a) z[intVars[liveInts[a]]] = ri[a];
};
// 5. Solve, round the integers nearest-first, re-solve.
std::vector<double> y(nf, 0.0);
std::vector<uint8_t> fixed(nf, 0);
bool stop = false;
if (useIntBlock) factorInts(fixed);
int iters = conjugateGradients(op, rhs, fixed, y, 1e-4, 2000, cancelled, stop, precond);
if (stop) return false;
// Before rounding: scale the map so its area (the number of unit squares, i.e. quads) is the wanted count. The
// constraints are homogeneous, so a scaled solution is still a solution; distortion near singularities and
// features otherwise leaves the count 10-20% off.
if (out.wantQuads > 0.0) {
double area = 0.0;
std::vector<Term> terms;
auto at = [&](uint32_t corner, int coord) {
double k;
expand(U(corner) + uint32_t(coord), terms, k);
double s = k;
for (const Term& t : terms) s += t.a * y[t.var];
return s;
};
for (uint32_t t = 0; t < nt; ++t) {
const double ax = at(3 * t, 0), ay = at(3 * t, 1), bx = at(3 * t + 1, 0), by = at(3 * t + 1, 1);
const double cx = at(3 * t + 2, 0), cy = at(3 * t + 2, 1);
area += 0.5 * std::abs((bx - ax) * (cy - ay) - (cx - ax) * (by - ay));
}
if (area > 0.0) {
const double s = std::sqrt(out.wantQuads / area);
for (double& v : y) v *= s;
for (double& v : rhs) v *= s;
if (timing) std::fprintf(stderr, " grid map: area %.0f, scaled by %.3f\n", area, s);
}
}
std::vector<uint32_t> intFree;
for (size_t i = 0; i < nf; ++i)
if (el.kind(freeVars[i]) != 0) intFree.push_back(uint32_t(i));
size_t rounds = 0;
{
std::vector<uint32_t> left = intFree;
while (!left.empty()) {
std::vector<std::pair<double, uint32_t>> dist;
for (uint32_t i : left) dist.push_back({std::abs(y[i] - std::round(y[i])), i});
std::sort(dist.begin(), dist.end());
static const double frac = std::getenv("SF_QR2_ROUND") ? std::atof(std::getenv("SF_QR2_ROUND")) : 0.7;
size_t take = std::max<size_t>(1, size_t(double(left.size()) * frac + 0.999));
while (take < dist.size() && dist[take].first < 0.08) ++take;
if (left.size() <= 8) take = left.size();
for (size_t k = 0; k < take; ++k) {
const uint32_t i = dist[k].second;
y[i] = std::round(y[i]);
fixed[i] = 1;
}
std::vector<uint32_t> rest;
for (size_t k = take; k < dist.size(); ++k) rest.push_back(dist[k].second);
left.swap(rest);
static const double midTol = std::getenv("SF_QR2_TOL") ? std::atof(std::getenv("SF_QR2_TOL")) : 1e-2;
if (useIntBlock) factorInts(fixed);
iters += conjugateGradients(op, rhs, fixed, y, left.empty() ? 1e-4 : midTol, left.empty() ? 2000 : 500, cancelled, stop, precond);
if (stop) return false;
++rounds;
}
}
if (timing)
std::fprintf(stderr, " grid map: %zu free unknowns (%zu integer), %zu rounding rounds, %d CG iterations\n", nf,
intFree.size(), rounds, iters);
// 6. The map at each corner.
out.uv.assign(nc, vec2(0.0f));
std::vector<Term> terms;
for (uint32_t c = 0; c < nc; ++c) {
double val[2];
for (int coord = 0; coord < 2; ++coord) {
double k;
expand(U(c) + uint32_t(coord), terms, k);
double s = k;
for (const Term& t : terms) s += t.a * y[t.var];
val[coord] = s;
}
out.uv[c] = vec2(float(val[0]), float(val[1]));
}
if (timing) {
double worst = 0.0;
size_t off = 0;
for (uint32_t c = 0; c < nc; ++c) {
if (!p.feature[c]) continue;
const uint32_t t = c / 3, k = c % 3;
const vec3 e = p.P[p.T[t][(k + 1) % 3]] - p.P[p.T[t][k]];
const int coord = axisOfEdge(t, e) == 0 ? 1 : 0;
for (uint32_t cc : {c, 3 * t + (k + 1) % 3}) {
const double v = coord ? out.uv[cc].y : out.uv[cc].x;
const double d = std::abs(v - std::round(v));
worst = std::max(worst, d);
off += d > 0.01;
}
}
std::fprintf(stderr, " grid map: feature corners off their lattice line: %zu (worst %.3f)\n", off, worst);
}
out.flipped = 0;
for (uint32_t t = 0; t < nt; ++t) {
const vec2 a = out.uv[3 * t], b = out.uv[3 * t + 1], c = out.uv[3 * t + 2];
const float area = (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
if (!(area > 0.0f)) ++out.flipped;
}
if (timing) {
std::vector<uint8_t> fv(nv, 0);
for (uint32_t c = 0; c < nc; ++c)
if (p.feature[c]) fv[p.T[c / 3][c % 3]] = fv[p.T[c / 3][(c % 3 + 1) % 3]] = 1;
size_t nearF = 0, nearS = 0;
for (uint32_t t = 0; t < nt; ++t) {
const vec2 a = out.uv[3 * t], b = out.uv[3 * t + 1], c = out.uv[3 * t + 2];
if ((b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y) > 0.0f) continue;
bool f2 = false, s2 = false;
for (int k = 0; k < 3; ++k) f2 |= fv[p.T[t][k]] != 0, s2 |= field.vertexIndex[p.T[t][k]] != 0;
nearF += f2, nearS += s2;
}
std::fprintf(stderr, " grid map: flipped triangles touching a feature %zu, a singularity %zu\n", nearF, nearS);
}
out.cutEdges = cutEdges;
out.integerVars = intFree.size();
return true;
}
} // namespace sf::qr2