Skip to content

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.

120 KB
Raw Blame
// SculptForge - open source digital sculpting
// SPDX-License-Identifier: GPL-3.0-or-later
#include "core/Multires.h"
#include "core/Micro.h"

#include "core/BVH.h"
#include "core/Document.h"
#include "core/PaintLayer.h"

#include <algorithm>
#include <atomic>
#include <cmath>
#include <cstring>
#include <limits>
#include <numbers>
#include <optional>
#include <thread>
#include <unordered_map>

#if defined(_WIN32)
#ifndef NOMINMAX
#define NOMINMAX
#endif
#ifndef WIN32_LEAN_AND_MEAN
#define WIN32_LEAN_AND_MEAN
#endif
#include <windows.h>
#else
#include <unistd.h>
#endif

namespace sf {

namespace {

constexpr uint32_t kNone = SubdivTopology::kNone;

// Runs fn(begin, end) over [0, n) on several threads for big meshes.
template <class Fn>
void parallelRange(size_t n, Fn fn) {
    const size_t threads = n < 100000 ? 1 : std::clamp<size_t>(std::thread::hardware_concurrency(), 1, 16);
    if (threads <= 1) {
        if (n) fn(size_t(0), n);
        return;
    }
    std::vector<std::thread> pool;
    const size_t chunk = (n + threads - 1) / threads;
    for (size_t t = 0; t < threads; ++t) {
        const size_t b = t * chunk, e = std::min(n, b + chunk);
        if (b < e) pool.emplace_back([=] { fn(b, e); });
    }
    for (auto& th : pool) th.join();
}

template <class T>
bool sameArray(const std::vector<T>& a, const std::vector<T>& b) {
    return a.size() == b.size() && (a.empty() || std::memcmp(a.data(), b.data(), a.size() * sizeof(T)) == 0);
}

// The level's data without topology, normals, texture or stack: what a level stores. (Add new Mesh attributes
// here too, so they follow the levels.)
// Copies the level arrays of `m` (all but the triangles) over `out`.
void assignLevelArrays(Mesh& out, const Mesh& m) {
    out.positions = m.positions;
    out.mask = m.mask;
    out.colors = m.colors;
    out.facegroups = m.facegroups;
    out.hidden = m.hidden;
    out.uvs = m.uvs;
    out.quadPartners = m.quadPartners;
    out.base = m.base;
    out.layers = m.layers;
    out.paintBase = m.paintBase;
    out.paintLayers = m.paintLayers;
    out.activePaintLayer = m.activePaintLayer;
}
Mesh leanCopy(const Mesh& m) {
    Mesh out;
    out.triangles = m.triangles;
    assignLevelArrays(out, m);
    return out;
}
std::shared_ptr<Mesh> leanShared(const Mesh& m) { return std::make_shared<Mesh>(leanCopy(m)); }

bool generatedLevel(const SubdivLevel& l) { return l.topo && l.topo->generated; }

// True when `tris` are exactly the triangles generateFaces makes for `tp` (compared polygon by polygon, in parallel).
bool matchesGenerated(const SubdivTopology& tp, const std::vector<glm::uvec3>& tris);

// What level `l` stores of the working mesh `w` (its current level): every level array, and the triangles and
// quad pairs only when they don't follow from the topology.
std::shared_ptr<Mesh> levelData(const Mesh& w, const SubdivLevel& l) {
    auto out = std::make_shared<Mesh>();
    assignLevelArrays(*out, w);
    if (!generatedLevel(l)) {
        out->triangles = w.triangles;
        return out;
    }
    if (!w.quadPartners.empty()) { // kept only if they differ from the generated pairs
        bool same = w.quadPartners.size() == w.triangles.size() && l.topo->catmullClark;
        for (size_t t = 0; t < w.quadPartners.size() && same; ++t) same = w.quadPartners[t] == uint32_t(t ^ 1);
        if (same) std::vector<uint32_t>().swap(out->quadPartners);
    } else if (l.topo->catmullClark) {
        out->quadPartners.assign(w.triangles.size(), Mesh::kNoQuad); // all pairs removed: keep that
    }
    return out;
}

// The triangles of level `l`: its own, or generated into `scratch`.
const std::vector<glm::uvec3>& levelTriangles(const SubdivLevel& l, std::vector<glm::uvec3>& scratch) {
    if (!generatedLevel(l)) return l.data->triangles;
    generateFaces(*l.topo, scratch, nullptr);
    return scratch;
}

// A working copy of level `l` (no topology yet): its arrays with its triangles and quad pairs.
Mesh levelWorkingCopy(const SubdivLevel& l) {
    Mesh out = leanCopy(*l.data);
    if (generatedLevel(l)) generateFaces(*l.topo, out.triangles, out.quadPartners.empty() ? &out.quadPartners : nullptr);
    return out;
}

// The shape channel subdivision and details work on: the positions, or the layer base while sculpt layers exist.
std::vector<glm::vec3>& baseChannel(Mesh& m) { return m.layers.empty() ? m.positions : m.base; }
const std::vector<glm::vec3>& baseChannel(const Mesh& m) { return m.layers.empty() ? m.positions : m.base; }

void evaluateLayers(Mesh& m) {
    if (m.layers.empty()) return;
    parallelRange(m.positions.size(), [&](size_t b, size_t e) {
        for (size_t v = b; v < e; ++v) {
            glm::vec3 p = m.base[v];
            for (const auto& l : m.layers) p += l.weight * l.delta[v];
            m.positions[v] = p;
        }
    });
}

// --- Copy-on-write access ---
MultiresStack& mutableStack(Mesh& m) {
    if (m.multires.use_count() > 1) m.multires = std::make_shared<MultiresStack>(*m.multires);
    return *m.multires;
}
Mesh& mutableData(SubdivLevel& l) {
    if (l.data.use_count() > 1) l.data = std::make_shared<Mesh>(*l.data);
    return *l.data;
}
std::vector<glm::vec3>& mutableArray(std::shared_ptr<std::vector<glm::vec3>>& a, size_t size) {
    if (!a) a = std::make_shared<std::vector<glm::vec3>>(size, glm::vec3(0.0f));
    else if (a.use_count() > 1) a = std::make_shared<std::vector<glm::vec3>>(*a);
    if (a->size() != size) a->resize(size, glm::vec3(0.0f));
    return *a;
}

// --- Topology ---

uint32_t polySize(const SubdivTopology& tp, size_t p) { return tp.polyOffsets[p + 1] - tp.polyOffsets[p]; }

// Polygons, edges and vertex -> edge lists of `coarse` with the given quad pairing (empty = all triangles).
// Pairs that aren't valid quads are treated as triangles (and dropped from tp.pairing).
// Which edge of triangle t is the diagonal it shares with u (as Mesh::quadDiagonal), on a bare triangle list.
int quadDiagonalOf(const std::vector<glm::uvec3>& tris, uint32_t t, uint32_t u) {
    if (t == u || t >= tris.size() || u >= tris.size()) return -1;
    const glm::uvec3& a = tris[t];
    const glm::uvec3& b = tris[u];
    if (a.x == a.y || a.y == a.z || a.x == a.z || b.x == b.y || b.y == b.z || b.x == b.z) return -1;
    for (int e = 0; e < 3; ++e)
        for (int k = 0; k < 3; ++k)
            if (b[k] == a[(e + 1) % 3] && b[(k + 1) % 3] == a[e]) return b[(k + 2) % 3] == a[(e + 2) % 3] ? -1 : e;
    return -1;
}

std::shared_ptr<SubdivTopology> buildCoarse(const std::vector<glm::uvec3>& triangles, uint32_t nv,
                                            std::vector<uint32_t> pairing, bool cc, bool smooth) {
    auto tp = std::make_shared<SubdivTopology>();
    tp->catmullClark = cc;
    tp->smooth = smooth;
    const uint32_t nt = uint32_t(triangles.size());
    tp->coarseVertices = nv;
    if (pairing.size() != nt) pairing.clear();
    bool anyPair = false;
    for (uint32_t t = 0; t < pairing.size(); ++t) {
        const uint32_t u = pairing[t];
        if (u == kNone) continue;
        if (u >= nt || pairing[u] != t || quadDiagonalOf(triangles, t, u) < 0) pairing[t] = kNone;
        else anyPair = true;
    }
    for (uint32_t t = 0; t < pairing.size(); ++t)
        if (pairing[t] != kNone && pairing[pairing[t]] != t) pairing[t] = kNone;
    if (!anyPair) pairing.clear();

    tp->polyOffsets.reserve(nt + 1);
    tp->polyOffsets.push_back(0);
    tp->polyVerts.reserve(nt * 3);
    tp->polyDiag.reserve(nt);
    tp->polyTris.reserve(nt);
    for (uint32_t t = 0; t < nt; ++t) {
        const uint32_t u = pairing.empty() ? kNone : pairing[t];
        const glm::uvec3& a = triangles[t];
        if (u == kNone) {
            if (a.x == a.y || a.y == a.z || a.x == a.z) tp->nonManifold = true; // degenerate: no implicit adjacency
            for (uint32_t c = 0; c < 3; ++c) {
                tp->polyVerts.push_back(a[c]);
            }
            tp->polyTris.push_back({t, kNone});
            tp->polyDiag.push_back(0);
        } else {
            if (u < t) continue;
            const int e = quadDiagonalOf(triangles, t, u);
            const glm::uvec3& b = triangles[u];
            uint32_t opposite = 0; // (not "far": a macro in windows.h)
            for (uint32_t k = 0; k < 3; ++k)
                if (b[k] != a[0] && b[k] != a[1] && b[k] != a[2]) opposite = k;
            for (int c : {(e + 1) % 3, (e + 2) % 3, e}) {
                tp->polyVerts.push_back(a[c]);
            }
            tp->polyVerts.push_back(b[opposite]);
            tp->polyTris.push_back({t, u});
            tp->polyDiag.push_back(uint8_t(e | opposite << 2));
        }
        tp->polyOffsets.push_back(uint32_t(tp->polyVerts.size()));
    }
    tp->quads = anyPair;
    // Exact sizes: the polygon lists were reserved for all triangles.
    tp->polyOffsets.shrink_to_fit();
    tp->polyVerts.shrink_to_fit();
    tp->polyTris.shrink_to_fit();
    tp->polyDiag.shrink_to_fit();

    // Edges: half-edges bucketed by their lower vertex, then matched within each (small) bucket.
    const size_t np = tp->polygonCount();
    std::vector<uint32_t> bucket(size_t(nv) + 1, 0);
    for (size_t p = 0; p < np; ++p)
        for (uint32_t i = tp->polyOffsets[p]; i < tp->polyOffsets[p + 1]; ++i) {
            const uint32_t a = tp->polyVerts[i], b = tp->polyVerts[i + 1 == tp->polyOffsets[p + 1] ? tp->polyOffsets[p] : i + 1];
            ++bucket[std::min(a, b) + 1];
        }
    for (size_t v = 0; v < nv; ++v) bucket[v + 1] += bucket[v];
    struct Half {
        uint32_t other, slot; // slot = index into polyVerts (the side starting there)
    };
    std::vector<Half> halves(bucket[nv]);
    {
        std::vector<uint32_t> cursor(bucket.begin(), bucket.end() - 1);
        for (size_t p = 0; p < np; ++p)
            for (uint32_t i = tp->polyOffsets[p]; i < tp->polyOffsets[p + 1]; ++i) {
                const uint32_t a = tp->polyVerts[i], b = tp->polyVerts[i + 1 == tp->polyOffsets[p + 1] ? tp->polyOffsets[p] : i + 1];
                halves[cursor[std::min(a, b)]++] = {std::max(a, b), i};
            }
    }
    std::vector<uint32_t> slotPoly(tp->polyVerts.size());
    for (size_t p = 0; p < np; ++p)
        for (uint32_t i = tp->polyOffsets[p]; i < tp->polyOffsets[p + 1]; ++i) slotPoly[i] = uint32_t(p);
    tp->polyEdges.assign(tp->polyVerts.size(), kNone);
    tp->edges.reserve(halves.size() / 2 + 16);
    tp->edgeFaces.reserve(halves.size() / 2 + 16);
    std::vector<uint8_t> faceCount;
    faceCount.reserve(halves.size() / 2 + 16);
    for (uint32_t v = 0; v < nv; ++v) {
        const uint32_t b0 = bucket[v], b1 = bucket[v + 1];
        for (uint32_t i = b0; i < b1; ++i) {
            uint32_t edge = kNone;
            for (uint32_t j = b0; j < i; ++j)
                if (halves[j].other == halves[i].other) {
                    edge = tp->polyEdges[halves[j].slot];
                    break;
                }
            const uint32_t poly = slotPoly[halves[i].slot];
            if (edge == kNone) {
                edge = uint32_t(tp->edges.size());
                tp->edges.push_back({v, halves[i].other});
                tp->edgeFaces.push_back({poly, kNone});
                faceCount.push_back(1);
            } else if (faceCount[edge]++ == 1) {
                tp->edgeFaces[edge].y = poly;
            } else {
                tp->edgeFaces[edge].y = kNone; // non-manifold: subdivided like a boundary (kept sharp)
            }
            tp->polyEdges[halves[i].slot] = edge;
        }
    }
    for (size_t e = 0; e < faceCount.size(); ++e)
        if (faceCount[e] > 2) {
            tp->edgeFaces[e].y = kNone;
            tp->nonManifold = true;
        }

    tp->vertEdgeOffsets.assign(size_t(nv) + 1, 0);
    for (const auto& e : tp->edges) {
        ++tp->vertEdgeOffsets[e.x + 1];
        ++tp->vertEdgeOffsets[e.y + 1];
    }
    for (size_t v = 0; v < nv; ++v) {
        tp->maxValence = std::max(tp->maxValence, tp->vertEdgeOffsets[v + 1]);
        tp->vertEdgeOffsets[v + 1] += tp->vertEdgeOffsets[v];
    }
    tp->vertEdges.resize(tp->vertEdgeOffsets[nv]);
    {
        std::vector<uint32_t> cursor(tp->vertEdgeOffsets.begin(), tp->vertEdgeOffsets.end() - 1);
        for (uint32_t e = 0; e < tp->edges.size(); ++e) {
            tp->vertEdges[cursor[tp->edges[e].x]++] = e;
            tp->vertEdges[cursor[tp->edges[e].y]++] = e;
        }
    }
    tp->fineVertices = nv + uint32_t(tp->edges.size()) + (cc ? uint32_t(np) : 0u);
    tp->fineTriangles = cc ? size_t(tp->polyVerts.size()) * 2 : np * 4;
    return tp;
}

// The coarse triangle of polygon `p` that holds side `side`: a quad (t[e+1], t[e+2], t[e], far) from buildCoarse
// has sides 0 and 1 on its first triangle and 2 and 3 on the one across the diagonal.
uint32_t sideTriangle(const SubdivTopology& tp, uint32_t p, uint32_t side) {
    const glm::uvec2 tris = tp.polyTris[p];
    return tris.y == kNone || side < 2 ? tris.x : tris.y;
}

// Per fine vertex: the neighbour that fixes its tangent direction (the next corner in the first triangle that
// has it). Built when details are fitted or applied rather than stored.
std::vector<uint32_t> frameRefs(uint32_t vertices, const std::vector<glm::uvec3>& fine) {
    std::vector<uint32_t> ref(vertices, kNone);
    for (const auto& t : fine)
        for (int c = 0; c < 3; ++c)
            if (ref[t[c]] == kNone) ref[t[c]] = t[(c + 1) % 3];
    return ref;
}

// Calls fn(f, polygon, coarse triangle, codes) for every fine triangle f in order (codes: 3 corner codes, see
// SubdivTopology), from the stored parents or, on a generated level, as generateFaces lays the triangles out.
template <class Fn>
void forEachFineFace(const SubdivTopology& tp, Fn fn) {
    if (!tp.generated) {
        for (size_t f = 0; f < tp.fineParentTri.size(); ++f) fn(f, tp.fineParentPoly[f], tp.fineParentTri[f], &tp.fineCode[f * 3]);
        return;
    }
    size_t f = 0;
    const size_t np = tp.polygonCount();
    for (uint32_t p = 0; p < np; ++p) {
        const uint32_t n = polySize(tp, p);
        if (tp.catmullClark) {
            for (uint32_t i = 0; i < n; ++i) {
                const uint32_t tri = sideTriangle(tp, p, i), prev = (i + n - 1) % n;
                const uint8_t a[3] = {uint8_t(i), uint8_t(4 + i), 8}, b[3] = {uint8_t(i), 8, uint8_t(4 + prev)};
                fn(f++, p, tri, a);
                fn(f++, p, tri, b);
            }
        } else {
            static constexpr uint8_t codes[4][3] = {{0, 4, 6}, {1, 5, 4}, {2, 6, 5}, {4, 5, 6}};
            const uint32_t tri = tp.polyTris[p].x;
            for (const auto& c : codes) fn(f++, p, tri, c);
        }
    }
}

} // namespace

void generateFaces(const SubdivTopology& tp, std::vector<glm::uvec3>& triangles, std::vector<uint32_t>* quadPartners) {
    const uint32_t nv = tp.coarseVertices, ne = uint32_t(tp.edges.size());
    const size_t np = tp.polygonCount();
    std::vector<glm::uvec3>().swap(triangles);
    triangles.resize(tp.fineTriangles);
    if (quadPartners) {
        std::vector<uint32_t>().swap(*quadPartners);
        if (tp.catmullClark) quadPartners->resize(tp.fineTriangles);
    }
    parallelRange(np, [&](size_t b, size_t e) {
        for (size_t p = b; p < e; ++p) {
            const uint32_t o = tp.polyOffsets[p], n = polySize(tp, p);
            auto corner = [&](uint32_t i) { return tp.polyVerts[o + i % n]; };
            auto edgePt = [&](uint32_t i) { return nv + tp.polyEdges[o + i % n]; };
            size_t f = tp.firstFineTriangle(p);
            if (tp.catmullClark) {
                const uint32_t c = nv + ne + uint32_t(p);
                for (uint32_t i = 0; i < n; ++i, f += 2) {
                    triangles[f] = {corner(i), edgePt(i), c};
                    triangles[f + 1] = {corner(i), c, edgePt(i + n - 1)};
                    if (quadPartners) {
                        (*quadPartners)[f] = uint32_t(f + 1);
                        (*quadPartners)[f + 1] = uint32_t(f);
                    }
                }
            } else {
                triangles[f] = {corner(0), edgePt(0), edgePt(2)};
                triangles[f + 1] = {corner(1), edgePt(1), edgePt(0)};
                triangles[f + 2] = {corner(2), edgePt(2), edgePt(1)};
                triangles[f + 3] = {edgePt(0), edgePt(1), edgePt(2)};
            }
        }
    });
}

namespace {

bool matchesGenerated(const SubdivTopology& tp, const std::vector<glm::uvec3>& tris) {
    if (tris.size() != tp.fineTriangles) return false;
    const uint32_t nv = tp.coarseVertices, ne = uint32_t(tp.edges.size());
    std::atomic<bool> same = true;
    parallelRange(tp.polygonCount(), [&](size_t b, size_t e) {
        for (size_t p = b; p < e && same.load(std::memory_order_relaxed); ++p) {
            const uint32_t o = tp.polyOffsets[p], n = polySize(tp, p);
            auto corner = [&](uint32_t i) { return tp.polyVerts[o + i % n]; };
            auto edgePt = [&](uint32_t i) { return nv + tp.polyEdges[o + i % n]; };
            const size_t f = tp.firstFineTriangle(p);
            bool ok = true;
            if (tp.catmullClark) {
                const uint32_t c = nv + ne + uint32_t(p);
                for (uint32_t i = 0; i < n && ok; ++i)
                    ok = tris[f + 2 * i] == glm::uvec3(corner(i), edgePt(i), c) &&
                         tris[f + 2 * i + 1] == glm::uvec3(corner(i), c, edgePt(i + n - 1));
            } else {
                ok = tris[f] == glm::uvec3(corner(0), edgePt(0), edgePt(2)) && tris[f + 1] == glm::uvec3(corner(1), edgePt(1), edgePt(0)) &&
                     tris[f + 2] == glm::uvec3(corner(2), edgePt(2), edgePt(1)) && tris[f + 3] == glm::uvec3(edgePt(0), edgePt(1), edgePt(2));
            }
            if (!ok) same = false;
        }
    });
    return same;
}

} // namespace

bool subdivImplicitAdjacency(const SubdivTopology& tp, const std::vector<glm::uvec3>& triangles) {
    return tp.generated && !tp.nonManifold && tp.maxValence <= IndexRing::kCapacity / 2 && matchesGenerated(tp, triangles);
}

namespace {

// True when the child maps number the fine vertices as a generated level does.
bool canonicalChildren(const SubdivTopology& tp) {
    const uint32_t nv = tp.coarseVertices, ne = uint32_t(tp.edges.size());
    if (tp.vertexChild.size() != nv || tp.edgeChild.size() != ne || tp.faceChild.size() != (tp.catmullClark ? tp.polygonCount() : 0))
        return false;
    for (uint32_t v = 0; v < nv; ++v)
        if (tp.vertexChild[v] != v) return false;
    for (uint32_t e = 0; e < ne; ++e)
        if (tp.edgeChild[e] != nv + e) return false;
    for (uint32_t p = 0; p < tp.faceChild.size(); ++p)
        if (tp.faceChild[p] != nv + ne + p) return false;
    return true;
}

// Makes `tp` a generated level (dropping its child maps and fine parents).
void markGenerated(SubdivTopology& tp) {
    tp.generated = true;
    std::vector<uint32_t>().swap(tp.vertexChild);
    std::vector<uint32_t>().swap(tp.edgeChild);
    std::vector<uint32_t>().swap(tp.faceChild);
    std::vector<uint32_t>().swap(tp.fineParentPoly);
    std::vector<uint32_t>().swap(tp.fineParentTri);
    std::vector<uint8_t>().swap(tp.fineCode);
}

// Parents and corner codes of arbitrary fine triangles from the child maps (reconstructed or loaded levels).
bool buildFineMetadata(SubdivTopology& tp, const std::vector<glm::uvec3>& fine, std::string& error) {
    const uint32_t nf = tp.fineVertices;
    std::vector<uint8_t> kind(nf, 255);
    std::vector<uint32_t> id(nf, kNone);
    auto mark = [&](const std::vector<uint32_t>& child, uint8_t k) {
        for (uint32_t i = 0; i < child.size(); ++i) {
            if (child[i] >= nf || kind[child[i]] != 255) return false;
            kind[child[i]] = k;
            id[child[i]] = i;
        }
        return true;
    };
    if (tp.vertexChild.size() != tp.coarseVertices || tp.edgeChild.size() != tp.edges.size() ||
        tp.faceChild.size() != (tp.catmullClark ? tp.polygonCount() : 0) || !mark(tp.vertexChild, 0) ||
        !mark(tp.edgeChild, 1) || !mark(tp.faceChild, 2)) {
        error = "the subdivision levels don't match";
        return false;
    }
    for (uint32_t v = 0; v < nf; ++v)
        if (kind[v] == 255) {
            error = "the subdivision levels don't match";
            return false;
        }
    const size_t nt = fine.size();
    tp.fineTriangles = nt;
    tp.fineParentPoly.assign(nt, kNone);
    tp.fineParentTri.assign(nt, kNone);
    tp.fineCode.assign(nt * 3, 0);
    std::atomic<bool> ok = true;
    parallelRange(nt, [&](size_t b, size_t e) {
        for (size_t f = b; f < e && ok.load(std::memory_order_relaxed); ++f) {
            const glm::uvec3& t = fine[f];
            uint32_t cand[3] = {kNone, kNone, kNone};
            for (int c = 0; c < 3 && cand[0] == kNone; ++c) {
                if (t[c] >= nf) break;
                if (kind[t[c]] == 1) {
                    cand[0] = tp.edgeFaces[id[t[c]]].x;
                    cand[1] = tp.edgeFaces[id[t[c]]].y;
                    // A non-manifold edge lists only one polygon here; also try the others it borders.
                } else if (kind[t[c]] == 2) {
                    cand[0] = id[t[c]];
                }
            }
            bool found = false;
            for (uint32_t p : cand) {
                if (p == kNone) continue;
                const uint32_t o = tp.polyOffsets[p], n = polySize(tp, p);
                uint8_t codes[3];
                bool all = true;
                for (int c = 0; c < 3 && all; ++c) {
                    const uint32_t v = t[c];
                    all = false;
                    if (kind[v] == 0) {
                        for (uint32_t i = 0; i < n; ++i)
                            if (tp.polyVerts[o + i] == id[v]) codes[c] = uint8_t(i), all = true;
                    } else if (kind[v] == 1) {
                        for (uint32_t i = 0; i < n; ++i)
                            if (tp.polyEdges[o + i] == id[v]) codes[c] = uint8_t(4 + i), all = true;
                    } else if (id[v] == p) {
                        codes[c] = 8, all = true;
                    }
                }
                if (!all) continue;
                int side = -1, e1 = -1, e2 = -1;
                for (int c = 0; c < 3; ++c) {
                    if (codes[c] < 4 && side < 0) side = codes[c];
                    if (codes[c] >= 4 && codes[c] < 8) (e1 < 0 ? e1 : e2) = codes[c] - 4;
                }
                if (side < 0 && e1 >= 0) side = e2 >= 0 && (uint32_t(e1) + 1) % n == uint32_t(e2) ? e2 : e1;
                tp.fineParentPoly[f] = p;
                tp.fineParentTri[f] = sideTriangle(tp, p, uint32_t(std::max(side, 0)));
                for (int c = 0; c < 3; ++c) tp.fineCode[f * 3 + size_t(c)] = codes[c];
                found = true;
                break;
            }
            if (!found) ok = false;
        }
    });
    if (!ok) {
        error = "the mesh is not a regular subdivision of the level below";
        return false;
    }
    return true;
}

// --- Stencils ---

// The subdivided field: the coarse values `P` through the level's stencils (Catmull-Clark / Loop when
// `smooth`, else linear: edge midpoints and polygon centres).
template <class T>
std::vector<T> subdivideField(const SubdivTopology& tp, bool smooth, const std::vector<T>& P) {
    std::vector<T> out(tp.fineVertices);
    const size_t np = tp.polygonCount(), ne = tp.edges.size();
    std::vector<T> fp;
    if (tp.catmullClark) {
        fp.resize(np);
        parallelRange(np, [&](size_t b, size_t e) {
            for (size_t p = b; p < e; ++p) {
                T sum = T(0);
                const uint32_t o = tp.polyOffsets[p], n = polySize(tp, p);
                for (uint32_t i = 0; i < n; ++i) sum += P[tp.polyVerts[o + i]];
                fp[p] = sum / float(n);
                out[tp.faceChildOf(uint32_t(p))] = fp[p];
            }
        });
    }
    auto opposite = [&](uint32_t p, uint32_t a, uint32_t b) {
        const uint32_t o = tp.polyOffsets[p];
        for (uint32_t i = 0; i < 3; ++i)
            if (tp.polyVerts[o + i] != a && tp.polyVerts[o + i] != b) return tp.polyVerts[o + i];
        return a;
    };
    parallelRange(ne, [&](size_t b, size_t e) {
        for (size_t i = b; i < e; ++i) {
            const uint32_t va = tp.edges[i].x, vb = tp.edges[i].y;
            const glm::uvec2 f = tp.edgeFaces[i];
            T v;
            if (!smooth || f.y == kNone) v = (P[va] + P[vb]) * 0.5f;
            else if (tp.catmullClark) v = (P[va] + P[vb] + fp[f.x] + fp[f.y]) * 0.25f;
            else v = (P[va] + P[vb]) * 0.375f + (P[opposite(f.x, va, vb)] + P[opposite(f.y, va, vb)]) * 0.125f;
            out[tp.edgeChildOf(uint32_t(i))] = v;
        }
    });
    parallelRange(tp.coarseVertices, [&](size_t b, size_t e) {
        for (size_t v = b; v < e; ++v) {
            const T& pv = P[v];
            T& o = out[tp.vertexChildOf(uint32_t(v))];
            const uint32_t e0 = tp.vertEdgeOffsets[v], e1 = tp.vertEdgeOffsets[v + 1], n = e1 - e0;
            if (!smooth || n == 0) {
                o = pv;
                continue;
            }
            uint32_t boundary = 0;
            T bsum = T(0), ring = T(0), faces = T(0);
            for (uint32_t k = e0; k < e1; ++k) {
                const uint32_t ei = tp.vertEdges[k];
                const uint32_t u = tp.edges[ei].x == v ? tp.edges[ei].y : tp.edges[ei].x;
                ring += P[u];
                if (tp.edgeFaces[ei].y == kNone) {
                    ++boundary;
                    bsum += P[u];
                } else if (tp.catmullClark) {
                    faces += (fp[tp.edgeFaces[ei].x] + fp[tp.edgeFaces[ei].y]) * 0.5f;
                }
            }
            if (boundary) {
                o = boundary == 2 ? pv * 0.75f + bsum * 0.125f : pv; // crease rule; corners stay put
            } else if (n < 3) {
                o = pv;
            } else if (tp.catmullClark) {
                const float fn = float(n);
                const T R = (pv * fn + ring) * (0.5f / fn), F = faces / fn;
                o = (F + R * 2.0f + pv * (fn - 3.0f)) / fn;
            } else {
                const float fn = float(n);
                const float c = 0.375f + 0.25f * std::cos(2.0f * std::numbers::pi_v<float> / fn);
                const float beta = (0.625f - c * c) / fn;
                o = pv * (1.0f - fn * beta) + ring * beta;
            }
        }
    });
    return out;
}

// Vertex normals of `Q` on the fine triangles (area weighted).
std::vector<glm::vec3> fineNormals(const std::vector<glm::uvec3>& tris, const std::vector<glm::vec3>& Q) {
    // Face normals in parallel, then summed per vertex in triangle order (so the result doesn't depend on the
    // thread count).
    std::vector<glm::vec3> f(tris.size());
    parallelRange(tris.size(), [&](size_t b, size_t e) {
        for (size_t i = b; i < e; ++i) {
            const glm::uvec3& t = tris[i];
            f[i] = glm::cross(Q[t.y] - Q[t.x], Q[t.z] - Q[t.x]);
        }
    });
    std::vector<glm::vec3> n(Q.size(), glm::vec3(0.0f));
    for (size_t i = 0; i < tris.size(); ++i) {
        const glm::uvec3& t = tris[i];
        n[t.x] += f[i];
        n[t.y] += f[i];
        n[t.z] += f[i];
    }
    return n;
}

// The local frame of fine vertex v: normal from `normal` (unnormalised sum), tangent towards its reference
// neighbour. Degenerate spots fall back to world axes.
inline void frameAt(glm::vec3 n, const glm::vec3& q, const glm::vec3& qref, glm::vec3& t, glm::vec3& b, glm::vec3& nn) {
    const float len = glm::length(n);
    if (!(len > 1e-30f)) {
        t = {1, 0, 0};
        b = {0, 1, 0};
        nn = {0, 0, 1};
        return;
    }
    n /= len;
    glm::vec3 d = qref - q;
    d -= n * glm::dot(n, d);
    const float dl = glm::length(d);
    if (dl > 1e-30f) d /= dl;
    else d = glm::normalize(std::abs(n.x) < 0.9f ? glm::cross(n, glm::vec3(1, 0, 0)) : glm::cross(n, glm::vec3(0, 1, 0)));
    t = d;
    b = glm::cross(n, d);
    nn = n;
}

// P[k] = Q + Frame(Q) * D, or D = Frame(Q)^-1 (P[k] - Q), with Q = the subdivided coarse shape and n its
// normals (fineNormals).
void applyDetail(const std::vector<uint32_t>& refs, const std::vector<glm::vec3>& n, const std::vector<glm::vec3>& Q,
                 const std::vector<glm::vec3>& D, std::vector<glm::vec3>& out) {
    out.resize(Q.size());
    parallelRange(Q.size(), [&](size_t b0, size_t e0) {
        for (size_t v = b0; v < e0; ++v) {
            glm::vec3 t, b, nn;
            const uint32_t r = refs[v];
            frameAt(n[v], Q[v], r == kNone ? Q[v] : Q[r], t, b, nn);
            out[v] = Q[v] + t * D[v].x + b * D[v].y + nn * D[v].z;
        }
    });
}
void fitDetail(const std::vector<uint32_t>& refs, const std::vector<glm::vec3>& n, const std::vector<glm::vec3>& Q,
               const std::vector<glm::vec3>& P, std::vector<glm::vec3>& D) {
    D.resize(Q.size());
    parallelRange(Q.size(), [&](size_t b0, size_t e0) {
        for (size_t v = b0; v < e0; ++v) {
            glm::vec3 t, b, nn;
            const uint32_t r = refs[v];
            frameAt(n[v], Q[v], r == kNone ? Q[v] : Q[r], t, b, nn);
            const glm::vec3 d = P[v] - Q[v];
            D[v] = {glm::dot(d, t), glm::dot(d, b), glm::dot(d, nn)};
        }
    });
}

// Sculpt-layer details live in the same local frames as the shape's (the frames of Q, the subdivided coarse
// base, with normals n = fineNormals(tris, Q)), so they turn with the surface. `out` += Frame(Q) * local.
void addLayerDetail(const std::vector<uint32_t>& refs, const std::vector<glm::vec3>& n, const std::vector<glm::vec3>& Q,
                    const std::vector<glm::vec3>& local, std::vector<glm::vec3>& out) {
    parallelRange(Q.size(), [&](size_t b0, size_t e0) {
        for (size_t v = b0; v < e0; ++v) {
            glm::vec3 t, b, nn;
            const uint32_t r = refs[v];
            frameAt(n[v], Q[v], r == kNone ? Q[v] : Q[r], t, b, nn);
            out[v] += t * local[v].x + b * local[v].y + nn * local[v].z;
        }
    });
}
// local = Frame(Q)^-1 * world.
void layerDetailToLocal(const std::vector<uint32_t>& refs, const std::vector<glm::vec3>& n, const std::vector<glm::vec3>& Q,
                        const std::vector<glm::vec3>& world, std::vector<glm::vec3>& local) {
    local.resize(Q.size());
    parallelRange(Q.size(), [&](size_t b0, size_t e0) {
        for (size_t v = b0; v < e0; ++v) {
            glm::vec3 t, b, nn;
            const uint32_t r = refs[v];
            frameAt(n[v], Q[v], r == kNone ? Q[v] : Q[r], t, b, nn);
            const glm::vec3 d = world[v];
            local[v] = {glm::dot(d, t), glm::dot(d, b), glm::dot(d, nn)};
        }
    });
}

// --- Moving attributes between neighbouring levels. `flags` (null = every element) say which elements
// changed; the ones written are flagged in `outFlags`. ---

template <class T>
void restrictVertices(const SubdivTopology& tp, const std::vector<T>& fine, std::vector<T>& coarse, T fill,
                      const std::vector<uint8_t>* flags, std::vector<uint8_t>& outFlags) {
    if (coarse.size() != tp.coarseVertices) coarse.assign(tp.coarseVertices, fill);
    outFlags.assign(tp.coarseVertices, 0);
    for (uint32_t v = 0; v < tp.coarseVertices; ++v) {
        const uint32_t f = tp.vertexChildOf(v);
        if (flags && !(*flags)[f]) continue;
        coarse[v] = fine[f];
        outFlags[v] = 1;
    }
}

template <class T>
void prolongVertices(const SubdivTopology& tp, const std::vector<T>& coarse, std::vector<T>& fine, T fill,
                     const std::vector<uint8_t>* flags, std::vector<uint8_t>& outFlags) {
    if (fine.size() != tp.fineVertices) {
        fine.assign(tp.fineVertices, fill);
        flags = nullptr;
    }
    outFlags.assign(tp.fineVertices, 0);
    auto on = [&](uint32_t v) { return !flags || (*flags)[v]; };
    for (uint32_t v = 0; v < tp.coarseVertices; ++v)
        if (on(v)) {
            fine[tp.vertexChildOf(v)] = coarse[v];
            outFlags[tp.vertexChildOf(v)] = 1;
        }
    for (size_t e = 0; e < tp.edges.size(); ++e) {
        const uint32_t a = tp.edges[e].x, b = tp.edges[e].y;
        if (!on(a) && !on(b)) continue;
        fine[tp.edgeChildOf(uint32_t(e))] = (coarse[a] + coarse[b]) * 0.5f;
        outFlags[tp.edgeChildOf(uint32_t(e))] = 1;
    }
    for (uint32_t p = 0; p < (tp.catmullClark ? tp.polygonCount() : 0); ++p) {
        const uint32_t o = tp.polyOffsets[p], n = polySize(tp, p);
        bool any = false;
        T sum = T(0);
        for (uint32_t i = 0; i < n; ++i) {
            any = any || on(tp.polyVerts[o + i]);
            sum += coarse[tp.polyVerts[o + i]];
        }
        if (!any) continue;
        fine[tp.faceChildOf(p)] = sum / float(n);
        outFlags[tp.faceChildOf(p)] = 1;
    }
}

// Paint layer colour and coverage together: midpoints average premultiplied, so unpainted (white,
// transparent) neighbours don't pale the edge (as subdividePaintLayers does).
void prolongPaintLayer(const SubdivTopology& tp, const PaintLayer& coarse, PaintLayer& fine,
                       const std::vector<uint8_t>* flags) {
    std::vector<uint8_t> dummy;
    std::vector<glm::vec3> premul(coarse.color.size());
    for (size_t v = 0; v < premul.size(); ++v) premul[v] = coarse.color[v] * coarse.alpha[v];
    std::vector<glm::vec3> fineColor = fine.color;
    std::vector<uint8_t> outFlags;
    prolongVertices(tp, coarse.alpha, fine.alpha, 0.0f, flags, outFlags);
    prolongVertices(tp, premul, fineColor, glm::vec3(1.0f), flags, dummy);
    if (fine.color.size() != tp.fineVertices) fine.color.assign(tp.fineVertices, glm::vec3(1.0f));
    for (uint32_t v = 0; v < tp.fineVertices; ++v)
        if (outFlags[v]) fine.color[v] = fine.alpha[v] > 0.0f ? fineColor[v] / fine.alpha[v] : glm::vec3(1.0f);
    for (uint32_t v = 0; v < tp.coarseVertices; ++v)
        if (!flags || (*flags)[v]) fine.color[tp.vertexChildOf(v)] = coarse.color[v]; // corners keep the exact colour
}

template <class T>
void restrictFaces(const SubdivTopology& tp, const std::vector<T>& fine, std::vector<T>& coarse, size_t coarseCount,
                   T fill, const std::vector<uint8_t>* flags, std::vector<uint8_t>& outFlags) {
    if (coarse.size() != coarseCount) coarse.assign(coarseCount, fill);
    outFlags.assign(coarseCount, 0);
    forEachFineFace(tp, [&](size_t f, uint32_t, uint32_t t, const uint8_t* code) {
        if (flags && !(*flags)[f]) return;
        // The child at a coarse corner speaks for its parent (centre children only when no corner child did).
        const bool cornerChild = code[0] < 4 || code[1] < 4 || code[2] < 4;
        if (outFlags[t] == 2 && !cornerChild) return;
        coarse[t] = fine[f];
        outFlags[t] = cornerChild ? 2 : 1;
    });
    for (auto& f : outFlags) f = f ? 1 : 0;
}

template <class T>
void prolongFaces(const SubdivTopology& tp, const std::vector<T>& coarse, std::vector<T>& fine, T fill,
                  const std::vector<uint8_t>* flags, std::vector<uint8_t>& outFlags) {
    const size_t nf = tp.fineTriangles;
    if (fine.size() != nf) {
        fine.assign(nf, fill);
        flags = nullptr;
    }
    outFlags.assign(nf, 0);
    forEachFineFace(tp, [&](size_t f, uint32_t, uint32_t t, const uint8_t*) {
        if (flags && !(*flags)[t]) return;
        fine[f] = coarse[t];
        outFlags[f] = 1;
    });
}

// UVs per triangle corner; `flags` are per triangle. `coarseTris`: the coarse level's triangles.
// Each coarse corner takes the UV of its fine vertex, which needs every UV seam on the coarse edges. A fine level
// unwrapped on its own (#145, @RodTDai's diagnosis: a high-poly imported with its UDIM layout) also has seams through
// coarse polygons, whose fine faces then lie in several islands; one UV per corner can't hold that, and copying each
// corner from its own fine face stretched faces across the layout. Such a polygon keeps one island: the one most
// of its fine faces are in (ties: the larger island, then the lower id, so a seam along a row of polygons moves to
// one side of it), and a corner of another island takes that island's UV at the same vertex where a fine face of
// the island touches it, else a least-squares affine fit of the island's UVs over the polygon, averaged over every
// polygon that needs the same vertex in the same island (so neighbours meet without cracks). Islands are fine faces
// joined across edges whose two ends have the same UVs on both sides: overlapping islands stay apart.
void restrictUvs(const SubdivTopology& tp, const std::vector<glm::uvec3>& coarseTris, const std::vector<glm::vec2>& fine,
                 std::vector<glm::vec2>& coarse, const std::vector<uint8_t>* flags, std::vector<uint8_t>& outFlags) {
    const size_t nt = coarseTris.size();
    if (coarse.size() != nt * 3) coarse.assign(nt * 3, glm::vec2(0.0f));
    outFlags.assign(nt, 0);
    auto put = [&](uint32_t p, uint32_t i, glm::vec2 uv) {
        const uint32_t cv = tp.polyVerts[tp.polyOffsets[p] + i];
        for (uint32_t t : {tp.polyTris[p].x, tp.polyTris[p].y}) {
            if (t == kNone) continue;
            for (uint32_t s = 0; s < 3; ++s)
                if (coarseTris[t][s] == cv) {
                    coarse[t * 3 + s] = uv;
                    outFlags[t] = 1;
                }
        }
    };
    const size_t np = tp.polygonCount(), nf = tp.fineTriangles;
    // Fine faces by polygon (CSR) with their corner codes.
    std::vector<uint32_t> parent(nf, kNone), offsets(np + 1, 0), faces(nf);
    std::vector<uint8_t> codes(nf * 3), touched(np, 0);
    forEachFineFace(tp, [&](size_t f, uint32_t p, uint32_t, const uint8_t* code) {
        parent[f] = p;
        for (int c = 0; c < 3; ++c) codes[f * 3 + size_t(c)] = code[c];
        if (!flags || (*flags)[f]) touched[p] = 1;
        ++offsets[p + 1];
    });
    for (size_t p = 0; p < np; ++p) offsets[p + 1] += offsets[p];
    {
        std::vector<uint32_t> cursor(offsets.begin(), offsets.end() - 1);
        for (uint32_t f = 0; f < nf; ++f)
            if (parent[f] != kNone) faces[cursor[parent[f]]++] = f;
    }
    auto same = [](glm::vec2 a, glm::vec2 b) { return glm::all(glm::lessThanEqual(glm::abs(a - b), glm::vec2(1e-6f))); };
    auto uvAt = [&](uint32_t f, int c) { return fine[size_t(f) * 3 + size_t(c)]; };
    // A polygon whose fine vertices each have one UV (no seam inside): its corners as before.
    std::vector<uint32_t> split;
    for (uint32_t p = 0; p < np; ++p) {
        if (!touched[p]) continue;
        glm::vec2 first[9];
        bool seen[9] = {}, clean = true;
        for (uint32_t k = offsets[p]; k < offsets[p + 1] && clean; ++k)
            for (int c = 0; c < 3 && clean; ++c) {
                const uint8_t code = codes[size_t(faces[k]) * 3 + size_t(c)];
                if (!seen[code]) seen[code] = true, first[code] = uvAt(faces[k], c);
                else clean = same(first[code], uvAt(faces[k], c));
            }
        if (!clean) {
            split.push_back(p);
            continue;
        }
        for (uint32_t i = 0; i < 4; ++i)
            if (seen[i]) put(p, i, first[i]);
    }
    if (split.empty()) return;

    // UV islands of the fine faces (union-find; a root is its island's lowest face).
    std::vector<uint32_t> root(nf);
    for (uint32_t f = 0; f < nf; ++f) root[f] = f;
    auto find = [&](uint32_t f) {
        while (root[f] != f) f = root[f] = root[root[f]];
        return f;
    };
    auto join = [&](uint32_t a, uint32_t b) {
        a = find(a), b = find(b);
        if (a != b) root[std::max(a, b)] = std::min(a, b);
    };
    // Joined when the shared edge's two ends have the same UVs in both faces. Inside a polygon: the codes they share;
    // across polygons: the halves of coarse edges (corner to edge point), each kept by the first face that has it.
    const size_t ne = tp.edges.size();
    std::vector<uint32_t> halfFace(ne * 2, kNone);
    std::vector<glm::vec2> halfUv(ne * 4);
    for (uint32_t p = 0; p < np; ++p) {
        const uint32_t o = tp.polyOffsets[p], n = polySize(tp, p);
        for (uint32_t k = offsets[p]; k < offsets[p + 1]; ++k) {
            const uint32_t f = faces[k];
            const uint8_t* cf = &codes[size_t(f) * 3];
            for (uint32_t l = k + 1; l < offsets[p + 1]; ++l) {
                const uint32_t g = faces[l];
                const uint8_t* cg = &codes[size_t(g) * 3];
                int shared = 0, match = 0;
                for (int a = 0; a < 3; ++a)
                    for (int b = 0; b < 3; ++b)
                        if (cf[a] == cg[b]) ++shared, match += same(uvAt(f, a), uvAt(g, b));
                if (shared == 2 && match == 2) join(f, g);
            }
            for (int a = 0; a < 3; ++a) {
                const int b = (a + 1) % 3;
                int corner = cf[a] < 4 ? a : cf[b] < 4 ? b : -1, mid = corner == a ? b : a;
                if (corner < 0 || cf[mid] < 4 || cf[mid] > 7) continue;
                const uint32_t i = cf[corner], side = cf[mid] - 4u;
                if (side != i && side != (i + n - 1) % n) continue;
                const uint32_t e = tp.polyEdges[o + side], h = e * 2 + (tp.edges[e].x == tp.polyVerts[o + i] ? 0u : 1u);
                if (halfFace[h] == kNone) {
                    halfFace[h] = f;
                    halfUv[h * 2] = uvAt(f, corner), halfUv[h * 2 + 1] = uvAt(f, mid);
                } else if (same(halfUv[h * 2], uvAt(f, corner)) && same(halfUv[h * 2 + 1], uvAt(f, mid))) {
                    join(halfFace[h], f);
                }
            }
        }
    }
    std::vector<uint32_t> islandSize(nf, 0);
    for (uint32_t f = 0; f < nf; ++f) ++islandSize[find(f)];

    // Where each fine corner sits in a polygon's parameter layout (for the affine fits).
    auto layout = [&](uint32_t n, uint8_t code) -> glm::vec2 {
        auto corner = [&](uint32_t i) {
            if (!tp.catmullClark) return i == 0 ? glm::vec2(0.0f) : i == 1 ? glm::vec2(1.0f, 0.0f) : glm::vec2(0.0f, 1.0f);
            const float a = 6.2831853f * float(i) / float(n);
            return glm::vec2(std::cos(a), std::sin(a));
        };
        if (code < 4) return corner(code);
        if (code < 8) return (corner(code - 4u) + corner((code - 3u) % n)) * 0.5f;
        return glm::vec2(0.0f);
    };
    // Per (coarse vertex, island): a UV of the island at that vertex (exact), or the sum and count of the fits.
    struct Shared {
        glm::vec2 uv{0.0f};
        int fits = 0;
        bool exact = false;
    };
    std::unordered_map<uint64_t, Shared> shared;
    struct Pending {
        uint32_t p, i;
        uint64_t key;
    };
    std::vector<Pending> pending;
    for (uint32_t p : split) {
        const uint32_t o = tp.polyOffsets[p], n = polySize(tp, p);
        // The island: most fine faces here, then the larger island, then the lower id.
        uint32_t island = kNone, most = 0;
        for (uint32_t k = offsets[p]; k < offsets[p + 1]; ++k) {
            const uint32_t r = find(faces[k]);
            uint32_t count = 0;
            for (uint32_t l = offsets[p]; l < offsets[p + 1]; ++l) count += find(faces[l]) == r;
            if (island == kNone || count > most || (count == most && (islandSize[r] > islandSize[island] ||
                                                                     (islandSize[r] == islandSize[island] && r < island))))
                island = r, most = count;
        }
        for (uint32_t i = 0; i < n; ++i) {
            bool done = false;
            for (uint32_t k = offsets[p]; k < offsets[p + 1] && !done; ++k)
                for (int c = 0; c < 3 && !done; ++c)
                    if (codes[size_t(faces[k]) * 3 + size_t(c)] == i && find(faces[k]) == island)
                        put(p, i, uvAt(faces[k], c)), done = true;
            if (done) continue;
            const uint32_t cv = tp.polyVerts[o + i];
            const uint64_t key = uint64_t(cv) << 32 | island;
            auto [it, fresh] = shared.try_emplace(key);
            Shared& sv = it->second;
            if (fresh) { // a fine face of the island at this vertex, in any polygon around it
                for (uint32_t x = tp.vertEdgeOffsets[cv]; x < tp.vertEdgeOffsets[cv + 1] && !sv.exact; ++x)
                    for (uint32_t q : {tp.edgeFaces[tp.vertEdges[x]].x, tp.edgeFaces[tp.vertEdges[x]].y}) {
                        if (q == kNone || sv.exact) continue;
                        for (uint32_t k = offsets[q]; k < offsets[q + 1] && !sv.exact; ++k)
                            for (int c = 0; c < 3 && !sv.exact; ++c) {
                                const uint8_t code = codes[size_t(faces[k]) * 3 + size_t(c)];
                                if (code < 4 && tp.polyVerts[tp.polyOffsets[q] + code] == cv && find(faces[k]) == island)
                                    sv.uv = uvAt(faces[k], c), sv.exact = true;
                            }
                    }
            }
            if (!sv.exact) { // uv = A (s, t, 1) by least squares over the island's fine corners in this polygon
                glm::mat3 m(0.0f);
                glm::mat3x2 r(0.0f); // columns: s, t, 1 -> the uv sums
                for (uint32_t k = offsets[p]; k < offsets[p + 1]; ++k) {
                    if (find(faces[k]) != island) continue;
                    for (int c = 0; c < 3; ++c) {
                        const glm::vec2 st = layout(n, codes[size_t(faces[k]) * 3 + size_t(c)]);
                        const glm::vec3 x(st, 1.0f);
                        m += glm::outerProduct(x, x);
                        r += glm::outerProduct(uvAt(faces[k], c), x);
                    }
                }
                if (std::abs(glm::determinant(m)) > 1e-6f) {
                    sv.uv += r * glm::inverse(m) * glm::vec3(layout(n, uint8_t(i)), 1.0f);
                    ++sv.fits;
                }
            }
            pending.push_back({p, i, key});
        }
    }
    for (const Pending& x : pending) {
        const Shared& sv = shared[x.key];
        if (sv.exact) put(x.p, x.i, sv.uv);
        else if (sv.fits) put(x.p, x.i, sv.uv / float(sv.fits));
        else // no fit: the corner's own UV
            for (uint32_t k = offsets[x.p]; k < offsets[x.p + 1]; ++k)
                for (int c = 0; c < 3; ++c)
                    if (codes[size_t(faces[k]) * 3 + size_t(c)] == x.i) put(x.p, x.i, uvAt(faces[k], c));
    }
}

void prolongUvs(const SubdivTopology& tp, const std::vector<glm::vec2>& coarse, std::vector<glm::vec2>& fine,
                const std::vector<uint8_t>* flags, std::vector<uint8_t>& outFlags) {
    const size_t nf = tp.fineTriangles;
    if (fine.size() != nf * 3) {
        fine.assign(nf * 3, glm::vec2(0.0f));
        flags = nullptr;
    }
    outFlags.assign(nf, 0);
    forEachFineFace(tp, [&](size_t f, uint32_t p, uint32_t, const uint8_t* code) {
        if (flags && !(*flags)[tp.polyTris[p].x] && (tp.polyTris[p].y == kNone || !(*flags)[tp.polyTris[p].y])) return;
        const uint32_t o = tp.polyOffsets[p], n = polySize(tp, p);
        auto cu = [&](uint32_t i) { return coarse[tp.polyCorner(p, i % n)]; };
        for (int c = 0; c < 3; ++c) {
            glm::vec2 uv;
            if (code[c] < 4) uv = cu(code[c]);
            else if (code[c] < 8) uv = (cu(code[c] - 4u) + cu(code[c] - 3u)) * 0.5f;
            else {
                uv = glm::vec2(0.0f);
                for (uint32_t i = 0; i < n; ++i) uv += cu(i);
                uv /= float(n);
            }
            fine[f * 3 + size_t(c)] = uv;
        }
        outFlags[f] = 1;
    });
}

// --- Levels ---

// Fine normals and frame references of level `l` on the subdivided shape Q, for its details' frames.
void levelFrames(const SubdivLevel& l, const std::vector<glm::vec3>& Q, std::vector<glm::vec3>& n, std::vector<uint32_t>& refs) {
    std::vector<glm::uvec3> scratch;
    const std::vector<glm::uvec3>& tris = levelTriangles(l, scratch);
    n = fineNormals(tris, Q);
    refs = frameRefs(l.topo->fineVertices, tris);
}

// Shape and sculpt layers of level k from level k-1 and its details. Its positions then stand for its detail,
// which is dropped (SubdivLevel::detail).
void evaluateLevel(MultiresStack& s, int k) {
    SubdivLevel& L = s.levels[size_t(k)];
    const Mesh& coarse = *s.levels[size_t(k) - 1].data;
    const SubdivTopology& tp = *L.topo;
    Mesh& fine = mutableData(L);
    const std::vector<glm::vec3> Q = subdivideField(tp, tp.smooth, baseChannel(coarse));
    std::vector<glm::vec3>& target = baseChannel(fine);
    std::vector<glm::vec3> n; // normals of Q, for the frames of the details
    std::vector<uint32_t> refs;
    if (L.detail) {
        levelFrames(L, Q, n, refs);
        applyDetail(refs, n, Q, *L.detail, target);
    } else {
        target = Q;
    }
    for (size_t i = 0; i < fine.layers.size() && i < coarse.layers.size(); ++i) {
        std::vector<glm::vec3> d = subdivideField(tp, tp.smooth, coarse.layers[i].delta);
        if (i < L.layerDetail.size() && L.layerDetail[i]) {
            if (n.empty()) levelFrames(L, Q, n, refs);
            addLayerDetail(refs, n, Q, *L.layerDetail[i], d);
        }
        fine.layers[i].delta = std::move(d);
    }
    evaluateLayers(fine);
    L.stale = false;
    L.detail.reset();
}

// Fits the detail of level `L` (not stale, no detail) to its positions on the level below, whose shape channel
// is `coarseBase`: done before that level changes, so this one can follow it.
void fitLevelDetail(SubdivLevel& L, const std::vector<glm::vec3>& coarseBase) {
    const SubdivTopology& tp = *L.topo;
    const std::vector<glm::vec3> Q = subdivideField(tp, tp.smooth, coarseBase);
    std::vector<glm::vec3> n;
    std::vector<uint32_t> refs;
    levelFrames(L, Q, n, refs);
    auto d = std::make_shared<std::vector<glm::vec3>>();
    fitDetail(refs, n, Q, baseChannel(*L.data), *d);
    L.detail = std::move(d);
}

} // namespace

struct SubdivLevelCache {
    struct Entry {
        std::shared_ptr<Mesh> key; // the level data the mesh was made from (held, so it can't change in place)
        std::shared_ptr<const SubdivTopology> topo; // that level's topology, when generated (its triangles follow)
        Mesh mesh;
        BVH bvh;
    };
    std::vector<Entry> entries; // most recently left last
    static constexpr size_t kMaxEntries = 2;
};

namespace {

// Makes the working mesh level `level` of its stack (levels up to it must be evaluated). `leaving` is the level
// the working mesh was (null data: don't keep it); with a BVH, that mesh and its BVH go to the level cache and
// a cached copy of the new level is used when there is one.
void enterLevel(Mesh& mesh, int level, BVH* bvh, const SubdivLevel* leavingLevel = nullptr) {
    std::shared_ptr<Mesh> leaving = leavingLevel ? leavingLevel->data : nullptr;
    std::shared_ptr<const SubdivTopology> leavingTopo = leavingLevel && generatedLevel(*leavingLevel) ? leavingLevel->topo : nullptr;
    std::shared_ptr<MultiresStack> stack = mesh.multires;
    if (leaving && leaving == stack->levels[size_t(level)].data) return; // already that level (e.g. Remove Below)
    if (!stack->cache) stack->cache = std::make_shared<SubdivLevelCache>();
    SubdivLevelCache& cache = *stack->cache;
    std::shared_ptr<PaintTexture> texture = mesh.texture;
    std::shared_ptr<const SelectionSetList> selectionSets = mesh.selectionSets; // (the Part's, not a level's)
    const bool toTexture = mesh.paintToTexture;
    const SubdivLevel& wantLevel = stack->levels[size_t(level)];
    const std::shared_ptr<Mesh> want = wantLevel.data;
    // A cached copy of this level: exact (same data), or with the same triangles (only the shape or attributes
    // changed, so its topology and BVH are kept and refitted).
    std::optional<SubdivLevelCache::Entry> taken;
    bool exact = false;
    if (bvh) {
        auto hit = std::find_if(cache.entries.begin(), cache.entries.end(), [&](const auto& e) { return e.key == want; });
        exact = hit != cache.entries.end();
        if (!exact)
            hit = std::find_if(cache.entries.begin(), cache.entries.end(), [&](const auto& e) {
                return generatedLevel(wantLevel) ? e.topo == wantLevel.topo : sameArray(e.mesh.triangles, want->triangles);
            });
        if (hit != cache.entries.end()) {
            taken = std::move(*hit);
            cache.entries.erase(hit);
        }
        if (leaving) {
            // Keep the mesh being left (it has its topology and BVH already) for stepping back.
            SubdivLevelCache::Entry e{std::move(leaving), std::move(leavingTopo), std::move(mesh), std::move(*bvh)};
            e.mesh.multires.reset();
            e.mesh.texture.reset();
            e.mesh.selectionSets.reset();
            cache.entries.push_back(std::move(e));
            while (cache.entries.size() > SubdivLevelCache::kMaxEntries) cache.entries.erase(cache.entries.begin());
        }
    }
    if (taken) {
        mesh = std::move(taken->mesh);
        *bvh = std::move(taken->bvh);
        if (!exact) {
            std::vector<uint32_t> moved;
            for (uint32_t v = 0; v < want->positions.size(); ++v)
                if (want->positions[v] != mesh.positions[v]) moved.push_back(v);
            assignLevelArrays(mesh, *want);
            if (generatedLevel(wantLevel) && wantLevel.topo->catmullClark && mesh.quadPartners.empty()) {
                mesh.quadPartners.resize(mesh.triangles.size()); // the generated pairs (2i, 2i + 1)
                for (size_t t = 0; t < mesh.quadPartners.size(); ++t) mesh.quadPartners[t] = uint32_t(t ^ 1);
            }
            mesh.sanitizeAttributes();
            mesh.recomputeAllNormals();
            if (hasPaintLayers(mesh)) compositePaintAll(mesh);
            bvh->refit(mesh, moved);
        }
    } else {
        mesh = levelWorkingCopy(wantLevel);
    }
    mesh.multires = std::move(stack);
    mesh.texture = std::move(texture);
    mesh.selectionSets = std::move(selectionSets);
    mesh.paintToTexture = toTexture;
    if (!taken) {
        mesh.rebuildTopology();
        mesh.recomputeAllNormals();
        if (hasPaintLayers(mesh)) compositePaintAll(mesh);
        if (bvh) bvh->build(mesh);
    }
    mesh.topologyDirty = true;
    mesh.facesDirty = true;
    mesh.markAllDirty();
}

bool sameLayerSet(const Mesh& a, const Mesh& b) {
    if (a.layers.size() != b.layers.size()) return false;
    for (size_t i = 0; i < a.layers.size(); ++i)
        if (a.layers[i].name != b.layers[i].name) return false;
    return true;
}
bool sameLayerWeights(const Mesh& a, const Mesh& b) {
    for (size_t i = 0; i < a.layers.size() && i < b.layers.size(); ++i)
        if (a.layers[i].weight != b.layers[i].weight) return false;
    return true;
}
bool samePaintSet(const Mesh& a, const Mesh& b) {
    if (a.paintLayers.size() != b.paintLayers.size() || a.paintBase.empty() != b.paintBase.empty()) return false;
    for (size_t i = 0; i < a.paintLayers.size(); ++i)
        if (a.paintLayers[i].name != b.paintLayers[i].name) return false;
    return true;
}
bool samePaintProperties(const Mesh& a, const Mesh& b) {
    if (a.activePaintLayer != b.activePaintLayer) return false;
    for (size_t i = 0; i < a.paintLayers.size() && i < b.paintLayers.size(); ++i) {
        const PaintLayer &x = a.paintLayers[i], &y = b.paintLayers[i];
        if (x.opacity != y.opacity || x.blend != y.blend || x.visible != y.visible || x.locked != y.locked) return false;
    }
    return true;
}

// Gives `m` (a level with `nv` vertices) the sculpt layer list of `w`, matching layers by name; new ones are zero.
void remapLayers(Mesh& m, std::vector<std::shared_ptr<std::vector<glm::vec3>>>* detail, const Mesh& w) {
    const size_t nv = m.positions.size();
    std::vector<SculptLayer> layers;
    std::vector<std::shared_ptr<std::vector<glm::vec3>>> details;
    std::vector<bool> used(m.layers.size(), false);
    for (const SculptLayer& wl : w.layers) {
        SculptLayer l{wl.name, {}, wl.weight};
        std::shared_ptr<std::vector<glm::vec3>> d;
        for (size_t i = 0; i < m.layers.size(); ++i)
            if (!used[i] && m.layers[i].name == wl.name) {
                used[i] = true;
                l.delta = std::move(m.layers[i].delta);
                if (detail && i < detail->size()) d = (*detail)[i];
                break;
            }
        if (l.delta.size() != nv) l.delta.assign(nv, glm::vec3(0.0f));
        layers.push_back(std::move(l));
        details.push_back(std::move(d));
    }
    if (m.layers.empty() && !layers.empty()) m.base = m.positions;
    m.layers = std::move(layers);
    if (m.layers.empty()) {
        if (m.base.size() == nv) m.positions = m.base; // the layers' offsets are dropped, as removeLayer does
        m.base.clear();
    }
    if (detail) *detail = std::move(details);
    evaluateLayers(m);
}

// Gives `m` the paint layer stack of `w` (names, order, settings), matching layers by name; new ones are transparent.
void remapPaint(Mesh& m, const Mesh& w) {
    const size_t nv = m.positions.size();
    if (w.paintLayers.empty()) {
        std::vector<PaintLayer>().swap(m.paintLayers);
        std::vector<glm::vec3>().swap(m.paintBase);
        m.activePaintLayer = -1;
        return;
    }
    if (m.paintBase.size() != nv) m.paintBase = m.colors.size() == nv ? m.colors : std::vector<glm::vec3>(nv, glm::vec3(1.0f));
    std::vector<PaintLayer> layers;
    std::vector<bool> used(m.paintLayers.size(), false);
    for (const PaintLayer& wl : w.paintLayers) {
        PaintLayer l = wl;
        l.color.clear();
        l.alpha.clear();
        for (size_t i = 0; i < m.paintLayers.size(); ++i)
            if (!used[i] && m.paintLayers[i].name == wl.name) {
                used[i] = true;
                l.color = std::move(m.paintLayers[i].color);
                l.alpha = std::move(m.paintLayers[i].alpha);
                break;
            }
        if (l.color.size() != nv) l.color.assign(nv, glm::vec3(1.0f));
        if (l.alpha.size() != nv) l.alpha.assign(nv, 0.0f);
        layers.push_back(std::move(l));
    }
    m.paintLayers = std::move(layers);
    m.activePaintLayer = w.activePaintLayer;
}

// Spreads a change of one per-vertex array from the current level `c` to every other level: copied down to
// the parent vertices, interpolated up where it changed. `get` picks the array from a level.
template <class T, class Get>
void spreadVertexArray(MultiresStack& s, int c, const std::vector<T>& w, const std::vector<T>& r, T fill, Get get) {
    const int n = int(s.levels.size());
    if (w.empty() && r.empty()) return;
    if (w.empty()) {
        for (int j = 0; j < n; ++j)
            if (j != c) std::vector<T>().swap(get(mutableData(s.levels[size_t(j)])));
        return;
    }
    std::vector<uint8_t> changed(w.size(), 0);
    bool any = false;
    for (size_t v = 0; v < w.size(); ++v)
        if (r.size() != w.size() ? !(w[v] == fill) : !(w[v] == r[v])) changed[v] = 1, any = true;
    if (!any && r.size() == w.size()) return;
    std::vector<uint8_t> flags = changed, next;
    const std::vector<T>* fine = &w;
    for (int j = c; j >= 1; --j) {
        std::vector<T>& coarse = get(mutableData(s.levels[size_t(j) - 1]));
        const bool fresh = coarse.empty();
        restrictVertices(*s.levels[size_t(j)].topo, *fine, coarse, fill, fresh ? nullptr : &flags, next);
        flags.swap(next);
        fine = &coarse;
    }
    flags = changed;
    const std::vector<T>* coarse = &w;
    for (int j = c + 1; j < n; ++j) {
        std::vector<T>& f = get(mutableData(s.levels[size_t(j)]));
        prolongVertices(*s.levels[size_t(j)].topo, *coarse, f, fill, &flags, next);
        flags.swap(next);
        coarse = &f;
    }
}

template <class T, class Get>
void spreadFaceArray(MultiresStack& s, int c, const std::vector<T>& w, const std::vector<T>& r, T fill, Get get) {
    const int n = int(s.levels.size());
    if (w.empty() && r.empty()) return;
    if (w.empty()) {
        for (int j = 0; j < n; ++j)
            if (j != c) std::vector<T>().swap(get(mutableData(s.levels[size_t(j)])));
        return;
    }
    std::vector<uint8_t> changed(w.size(), 0);
    bool any = false;
    for (size_t t = 0; t < w.size(); ++t)
        if (r.size() != w.size() ? !(w[t] == fill) : !(w[t] == r[t])) changed[t] = 1, any = true;
    if (!any && r.size() == w.size()) return;
    std::vector<uint8_t> flags = changed, next;
    const std::vector<T>* fine = &w;
    for (int j = c; j >= 1; --j) {
        const size_t coarseCount = s.levels[size_t(j) - 1].triangleCount();
        std::vector<T>& coarse = get(mutableData(s.levels[size_t(j) - 1]));
        const bool fresh = coarse.empty();
        restrictFaces(*s.levels[size_t(j)].topo, *fine, coarse, coarseCount, fill, fresh ? nullptr : &flags, next);
        flags.swap(next);
        fine = &coarse;
    }
    flags = changed;
    const std::vector<T>* coarse = &w;
    for (int j = c + 1; j < n; ++j) {
        std::vector<T>& f = get(mutableData(s.levels[size_t(j)]));
        prolongFaces(*s.levels[size_t(j)].topo, *coarse, f, fill, &flags, next);
        flags.swap(next);
        coarse = &f;
    }
}

void spreadUvs(MultiresStack& s, int c, const Mesh& w, const Mesh& r) {
    const int n = int(s.levels.size());
    if (w.uvs.empty() && r.uvs.empty()) return;
    if (w.uvs.empty()) {
        for (int j = 0; j < n; ++j)
            if (j != c) std::vector<glm::vec2>().swap(mutableData(s.levels[size_t(j)]).uvs);
        return;
    }
    const size_t nt = w.triangleCount();
    std::vector<uint8_t> changed(nt, 0);
    bool any = false;
    for (size_t t = 0; t < nt; ++t)
        if (r.uvs.size() != w.uvs.size() || w.uvs[t * 3] != r.uvs[t * 3] || w.uvs[t * 3 + 1] != r.uvs[t * 3 + 1] ||
            w.uvs[t * 3 + 2] != r.uvs[t * 3 + 2])
            changed[t] = 1, any = true;
    if (!any) return;
    std::vector<uint8_t> flags = changed, next;
    const std::vector<glm::vec2>* fine = &w.uvs;
    std::vector<glm::uvec3> scratch;
    for (int j = c; j >= 1; --j) {
        const std::vector<glm::uvec3>& coarseTris = levelTriangles(s.levels[size_t(j) - 1], scratch);
        Mesh& cm = mutableData(s.levels[size_t(j) - 1]);
        const bool fresh = cm.uvs.empty();
        restrictUvs(*s.levels[size_t(j)].topo, coarseTris, *fine, cm.uvs, fresh ? nullptr : &flags, next);
        flags.swap(next);
        fine = &cm.uvs;
    }
    flags = changed;
    const std::vector<glm::vec2>* coarse = &w.uvs;
    for (int j = c + 1; j < n; ++j) {
        std::vector<glm::vec2>& f = mutableData(s.levels[size_t(j)]).uvs;
        prolongUvs(*s.levels[size_t(j)].topo, *coarse, f, &flags, next);
        flags.swap(next);
        coarse = &f;
    }
}

// Shape: restrict the change of each channel down, re-fit the details of the levels below, and mark the
// levels above for re-evaluation.
void spreadShape(MultiresStack& s, int c, const Mesh& w, const Mesh& r) {
    const size_t channels = 1 + w.layers.size();
    bool anyChange = false;
    // Per level: the subdivided coarse base and its normals (the layer details' frames), once the base channel
    // (channel 0, done first) is final.
    std::vector<std::vector<glm::vec3>> frameQ(size_t(c) + 1), frameN(size_t(c) + 1);
    std::vector<std::vector<uint32_t>> frameRef(size_t(c) + 1);
    bool baseChanged = false;
    for (size_t ch = 0; ch < channels; ++ch) {
        const std::vector<glm::vec3>& wa = ch == 0 ? baseChannel(w) : w.layers[ch - 1].delta;
        const std::vector<glm::vec3>& ra = ch == 0 ? baseChannel(r) : r.layers[ch - 1].delta;
        const bool same = sameArray(wa, ra);
        // A changed base also changes the frames the layer details are kept in, so those are re-fitted too.
        if (same && !(ch > 0 && baseChanged)) continue;
        if (ch == 0) baseChanged = true;
        anyChange = true;
        // Restrict with full weighting (the transpose of linear interpolation): each coarse vertex moves by a
        // blend of the change at its own fine vertex (weight 1), the edge points around it (1/2) and, for
        // Catmull-Clark, the face points (1/4). Broad changes come through unchanged; narrow strokes show up
        // softened instead of as spikes.
        std::vector<glm::vec3> delta(same ? 0 : wa.size());
        parallelRange(delta.size(), [&](size_t b, size_t e) {
            for (size_t v = b; v < e; ++v) delta[v] = wa[v] - ra[v];
        });
        for (int j = same ? 0 : c; j >= 1; --j) {
            const SubdivTopology& tp = *s.levels[size_t(j)].topo;
            std::vector<glm::vec3> cd(tp.coarseVertices);
            parallelRange(tp.coarseVertices, [&](size_t b, size_t e) {
                for (size_t v = b; v < e; ++v) {
                    const uint32_t e0 = tp.vertEdgeOffsets[v], e1 = tp.vertEdgeOffsets[v + 1];
                    glm::vec3 sum = delta[tp.vertexChildOf(uint32_t(v))];
                    float weight = 1.0f;
                    for (uint32_t k = e0; k < e1; ++k) {
                        const uint32_t ei = tp.vertEdges[k];
                        sum += 0.5f * delta[tp.edgeChildOf(ei)];
                        weight += 0.5f;
                        if (!tp.catmullClark) continue;
                        // Each polygon around v borders two of its edges: a quarter weight, half from each.
                        for (uint32_t f : {tp.edgeFaces[ei].x, tp.edgeFaces[ei].y})
                            if (f != kNone) {
                                sum += 0.125f * delta[tp.faceChildOf(f)];
                                weight += 0.125f;
                            }
                    }
                    cd[v] = sum / weight;
                }
            });
            Mesh& cm = mutableData(s.levels[size_t(j) - 1]);
            std::vector<glm::vec3>& target = ch == 0 ? baseChannel(cm) : cm.layers[ch - 1].delta;
            for (size_t v = 0; v < cd.size(); ++v) target[v] += cd[v];
            delta = std::move(cd);
        }
        // The levels up to the current one keep their new positions, which stand for their details (dropped; see
        // SubdivLevel::detail). Sculpt-layer details are kept in the frames of the subdivided base, re-fitted
        // bottom-up so each level is exactly what it was (the current one exactly as sculpted).
        for (int j = 1; j <= c; ++j) {
            SubdivLevel& L = s.levels[size_t(j)];
            if (ch == 0) {
                L.detail.reset();
                continue;
            }
            const SubdivTopology& tp = *L.topo;
            const Mesh& cm = *s.levels[size_t(j) - 1].data;
            const Mesh& fm = j == c ? w : *L.data;
            const std::vector<glm::vec3>& fineVals = fm.layers[ch - 1].delta;
            std::vector<glm::vec3> Q = subdivideField(tp, tp.smooth, cm.layers[ch - 1].delta);
            if (L.layerDetail.size() < w.layers.size()) L.layerDetail.resize(w.layers.size());
            std::vector<glm::vec3>& fq = frameQ[size_t(j)];
            if (fq.empty()) {
                fq = subdivideField(tp, tp.smooth, baseChannel(cm));
                levelFrames(L, fq, frameN[size_t(j)], frameRef[size_t(j)]);
            }
            std::vector<glm::vec3> world(Q.size());
            for (size_t v = 0; v < Q.size(); ++v) world[v] = fineVals[v] - Q[v];
            layerDetailToLocal(frameRef[size_t(j)], frameN[size_t(j)], fq, world, mutableArray(L.layerDetail[ch - 1], Q.size()));
        }
    }
    if (!anyChange) return;
    for (int j = 0; j < c; ++j) evaluateLayers(mutableData(s.levels[size_t(j)]));
    // The levels above follow: each gets the detail that fits its positions on the level below as it was (the
    // current level's old shape is `r`; the ones above haven't changed yet), then waits to be evaluated.
    for (size_t j = size_t(c) + 1; j < s.levels.size(); ++j) {
        SubdivLevel& L = s.levels[j];
        if (!L.stale && !L.detail) fitLevelDetail(L, baseChannel(j == size_t(c) + 1 ? r : *s.levels[j - 1].data));
    }
    for (size_t j = size_t(c) + 1; j < s.levels.size(); ++j) s.levels[j].stale = true;
}

bool levelsDiffer(const Mesh& w, const Mesh& r) {
    if (!sameArray(w.positions, r.positions) || !sameArray(w.base, r.base) || !sameLayerSet(w, r) ||
        !sameLayerWeights(w, r) || !sameArray(w.mask, r.mask) || !sameArray(w.colors, r.colors) ||
        !sameArray(w.facegroups, r.facegroups) || !sameArray(w.hidden, r.hidden) || !sameArray(w.uvs, r.uvs) ||
        !samePaintSet(w, r) || !samePaintProperties(w, r) || !sameArray(w.paintBase, r.paintBase))
        return true;
    for (size_t i = 0; i < w.layers.size(); ++i)
        if (!sameArray(w.layers[i].delta, r.layers[i].delta)) return true;
    for (size_t i = 0; i < w.paintLayers.size(); ++i)
        if (!sameArray(w.paintLayers[i].color, r.paintLayers[i].color) ||
            !sameArray(w.paintLayers[i].alpha, r.paintLayers[i].alpha))
            return true;
    return false;
}

// The levels a mesh with no stack starts with: just itself.
MultiresStack& ensureStack(Mesh& mesh) {
    if (!mesh.multires) {
        mesh.multires = std::make_shared<MultiresStack>();
        mesh.multires->levels.push_back({leanShared(mesh), nullptr, nullptr, {}, false});
        mesh.multires->current = 0;
    }
    return mutableStack(mesh);
}

void dropStackIfSingle(Mesh& mesh) {
    if (mesh.multires && mesh.multires->levels.size() < 2) mesh.multires.reset();
}

// The fine level of a divide (generated: no triangles stored): every attribute from the coarse level.
std::shared_ptr<Mesh> divideData(const SubdivTopology& tp, const Mesh& coarse) {
    auto fine = std::make_shared<Mesh>();
    std::vector<uint8_t> f;
    if (coarse.layers.empty()) {
        fine->positions = subdivideField(tp, tp.smooth, coarse.positions);
    } else {
        fine->base = subdivideField(tp, tp.smooth, coarse.base);
        for (const SculptLayer& l : coarse.layers) fine->layers.push_back({l.name, subdivideField(tp, tp.smooth, l.delta), l.weight});
        fine->positions.resize(fine->base.size());
        evaluateLayers(*fine);
    }
    if (coarse.hasMask()) prolongVertices(tp, coarse.mask, fine->mask, 0.0f, nullptr, f);
    if (coarse.hasColors()) prolongVertices(tp, coarse.colors, fine->colors, glm::vec3(1.0f), nullptr, f);
    if (coarse.hasFaceGroups()) prolongFaces(tp, coarse.facegroups, fine->facegroups, 0u, nullptr, f);
    if (coarse.hasHidden()) prolongFaces(tp, coarse.hidden, fine->hidden, uint8_t(0), nullptr, f);
    if (coarse.hasUvs()) prolongUvs(tp, coarse.uvs, fine->uvs, nullptr, f);
    if (!coarse.paintLayers.empty()) {
        prolongVertices(tp, coarse.paintBase, fine->paintBase, glm::vec3(1.0f), nullptr, f);
        for (const PaintLayer& l : coarse.paintLayers) {
            PaintLayer nl = l;
            nl.color.clear();
            nl.alpha.clear();
            prolongPaintLayer(tp, l, nl, nullptr);
            fine->paintLayers.push_back(std::move(nl));
        }
        fine->activePaintLayer = coarse.activePaintLayer;
    }
    return fine;
}

} // namespace

std::vector<uint32_t> SubdivTopology::pairing() const {
    if (!quads) return {};
    std::vector<uint32_t> out(polygonCount() + std::count_if(polyTris.begin(), polyTris.end(), [](const glm::uvec2& t) { return t.y != kNone; }), kNone);
    for (const glm::uvec2& t : polyTris)
        if (t.y != kNone) {
            out[t.x] = t.y;
            out[t.y] = t.x;
        }
    return out;
}

size_t SubdivTopology::bytes() const {
    auto b = [](const auto& v) { return v.capacity() * sizeof(v[0]); };
    return b(polyOffsets) + b(polyVerts) + b(polyEdges) + b(polyDiag) + b(polyTris) + b(edges) +
           b(edgeFaces) + b(vertEdgeOffsets) + b(vertEdges) + b(vertexChild) + b(edgeChild) + b(faceChild) +
           b(fineParentPoly) + b(fineParentTri) + b(fineCode);
}

// --- Queries ---

int subdivLevelCount(const Mesh& mesh) { return mesh.multires ? int(mesh.multires->levels.size()) : 0; }
int subdivCurrentLevel(const Mesh& mesh) { return mesh.multires ? mesh.multires->current : 0; }

std::string subdivLevelText(const Mesh& mesh) {
    if (!mesh.multires) return {};
    return "Level " + std::to_string(mesh.multires->current + 1) + "/" + std::to_string(mesh.multires->levels.size());
}

size_t subdivLevelTriangles(const Mesh& mesh, int level) {
    if (!mesh.multires) return level == 0 ? mesh.triangleCount() : 0;
    if (level < 0 || level >= int(mesh.multires->levels.size())) return 0;
    return mesh.multires->levels[size_t(level)].triangleCount();
}

bool subdivMatches(const Mesh& mesh) {
    if (!mesh.multires) return true;
    const MultiresStack& s = *mesh.multires;
    if (s.current < 0 || s.current >= int(s.levels.size()) || !s.levels[size_t(s.current)].data) return false;
    const SubdivLevel& l = s.levels[size_t(s.current)];
    return l.data->vertexCount() == mesh.vertexCount() && l.triangleCount() == mesh.triangleCount();
}

size_t subdivBytes(const Mesh& mesh) {
    if (!mesh.multires) return 0;
    size_t total = 0;
    for (const SubdivLevel& l : mesh.multires->levels) {
        const Mesh& m = *l.data;
        total += m.positions.size() * sizeof(glm::vec3) * (1 + (m.base.empty() ? 0 : 1 + m.layers.size())) +
                 m.triangles.size() * sizeof(glm::uvec3) + m.mask.size() * 4 + m.colors.size() * 12 +
                 m.facegroups.size() * 4 + m.hidden.size() + m.uvs.size() * 8 + m.quadPartners.size() * 4 +
                 m.paintBase.size() * 12;
        for (const PaintLayer& p : m.paintLayers) total += p.color.size() * 12 + p.alpha.size() * 4;
        if (l.topo) total += l.topo->bytes();
        if (l.detail) total += l.detail->size() * sizeof(glm::vec3);
        for (const auto& d : l.layerDetail)
            if (d) total += d->size() * sizeof(glm::vec3);
    }
    return total;
}

size_t subdivCacheBytes(const Mesh& mesh) {
    if (!mesh.multires || !mesh.multires->cache) return 0;
    size_t total = 0;
    for (const SubdivLevelCache::Entry& e : mesh.multires->cache->entries) {
        const Mesh& m = e.mesh;
        // Positions, normals and the vertex adjacency; triangles, face normals, quads and the BVH (estimated).
        total += m.vertexCount() * 80 + m.triangleCount() * 48 + m.base.size() * 12 + m.mask.size() * 4 +
                 m.colors.size() * 12 + m.facegroups.size() * 4 + m.hidden.size() + m.uvs.size() * 8 +
                 m.paintBase.size() * 12;
        for (const SculptLayer& l : m.layers) total += l.delta.size() * 12;
        for (const PaintLayer& p : m.paintLayers) total += p.color.size() * 12 + p.alpha.size() * 4;
    }
    return total;
}

void subdivReleaseCache(Mesh& mesh) {
    // The cache is shared by every copy of the stack (undo steps): emptying it frees it for all of them.
    if (mesh.multires && mesh.multires->cache) std::vector<SubdivLevelCache::Entry>().swap(mesh.multires->cache->entries);
}

std::string subdivDroppedNote(const Mesh& mesh, const std::string& name) {
    if (!mesh.multires || mesh.multires->levels.size() < 2) return {};
    return "Subdivision levels removed: " + (name.empty() ? std::string() : name + " ") + "Level " +
           std::to_string(mesh.multires->current + 1) + " of " + std::to_string(mesh.multires->levels.size()) +
           " kept as the new base";
}

void notePartLevelsDropped(Document& doc, int index) {
    if (index < 0 || index >= doc.partCount()) return;
    const std::string note = subdivDroppedNote(doc.partMesh(index), doc.parts[size_t(index)].name);
    if (!note.empty()) doc.notice += (doc.notice.empty() ? "" : "; ") + note;
}

// --- Operations ---

bool subdivCommit(Mesh& w) {
    if (!w.multires) return true;
    const int c = w.multires->current;
    const std::shared_ptr<Mesh> rp = w.multires->levels[size_t(c)].data;
    const Mesh& r0 = *rp;
    const SubdivLevel& cl = w.multires->levels[size_t(c)];
    if (w.vertexCount() != r0.vertexCount() ||
        !(generatedLevel(cl) ? matchesGenerated(*cl.topo, w.triangles) : sameArray(w.triangles, r0.triangles))) {
        w.multires.reset(); // the topology changed under the stack: the levels no longer apply
        return false;
    }
    if (!levelsDiffer(w, r0)) return true;
    MultiresStack& s = mutableStack(w);
    const int n = int(s.levels.size());

    // Sculpt and paint layer sets first, so every level has the current level's lists (r = the old current
    // level with the new lists, to diff against).
    Mesh remapped;
    const Mesh* r = &r0;
    if (!sameLayerSet(w, r0) || !samePaintSet(w, r0)) {
        remapped = leanCopy(r0);
        if (!sameLayerSet(w, r0)) {
            // `remapped` also carries the current level's layer details through the same name mapping.
            remapLayers(remapped, c > 0 ? &s.levels[size_t(c)].layerDetail : nullptr, w);
            for (int j = 0; j < n; ++j)
                if (j != c) remapLayers(mutableData(s.levels[size_t(j)]), &s.levels[size_t(j)].layerDetail, w);
        }
        if (!samePaintSet(w, r0)) {
            remapPaint(remapped, w);
            for (int j = 0; j < n; ++j)
                if (j != c) remapPaint(mutableData(s.levels[size_t(j)]), w);
        }
        r = &remapped;
    }
    if (!sameLayerWeights(w, *r)) {
        for (int j = 0; j < n; ++j) {
            if (j == c) continue;
            Mesh& m = mutableData(s.levels[size_t(j)]);
            for (size_t i = 0; i < m.layers.size() && i < w.layers.size(); ++i) m.layers[i].weight = w.layers[i].weight;
            if (!s.levels[size_t(j)].stale) evaluateLayers(m);
        }
    }
    if (!samePaintProperties(w, *r)) {
        for (int j = 0; j < n; ++j) {
            if (j == c) continue;
            Mesh& m = mutableData(s.levels[size_t(j)]);
            m.activePaintLayer = w.activePaintLayer;
            for (size_t i = 0; i < m.paintLayers.size() && i < w.paintLayers.size(); ++i) {
                m.paintLayers[i].opacity = w.paintLayers[i].opacity;
                m.paintLayers[i].blend = w.paintLayers[i].blend;
                m.paintLayers[i].visible = w.paintLayers[i].visible;
                m.paintLayers[i].locked = w.paintLayers[i].locked;
            }
        }
    }

    spreadShape(s, c, w, *r);
    spreadVertexArray(s, c, w.mask, r->mask, 0.0f, [](Mesh& m) -> std::vector<float>& { return m.mask; });
    if (w.paintLayers.empty()) {
        spreadVertexArray(s, c, w.colors, r->colors, glm::vec3(1.0f), [](Mesh& m) -> std::vector<glm::vec3>& { return m.colors; });
    } else {
        spreadVertexArray(s, c, w.paintBase, r->paintBase, glm::vec3(1.0f),
                          [](Mesh& m) -> std::vector<glm::vec3>& { return m.paintBase; });
        for (size_t i = 0; i < w.paintLayers.size(); ++i) {
            spreadVertexArray(s, c, w.paintLayers[i].color, r->paintLayers[i].color, glm::vec3(1.0f),
                              [i](Mesh& m) -> std::vector<glm::vec3>& { return m.paintLayers[i].color; });
            spreadVertexArray(s, c, w.paintLayers[i].alpha, r->paintLayers[i].alpha, 0.0f,
                              [i](Mesh& m) -> std::vector<float>& { return m.paintLayers[i].alpha; });
        }
        for (int j = 0; j < n; ++j)
            if (j != c && hasPaintLayers(*s.levels[size_t(j)].data)) compositePaintAll(mutableData(s.levels[size_t(j)]));
    }
    spreadFaceArray(s, c, w.facegroups, r->facegroups, 0u, [](Mesh& m) -> std::vector<uint32_t>& { return m.facegroups; });
    spreadFaceArray(s, c, w.hidden, r->hidden, uint8_t(0), [](Mesh& m) -> std::vector<uint8_t>& { return m.hidden; });
    spreadUvs(s, c, w, *r);

    s.levels[size_t(c)].data = levelData(w, s.levels[size_t(c)]);
    return true;
}

bool subdivSetLevel(Mesh& mesh, int level, std::string& error, BVH* bvh) {
    if (!mesh.multires) {
        error = "This Part has no subdivision levels (Divide adds them)";
        return false;
    }
    if (mesh.micro && level != mesh.multires->current) {
        error = "This Part has a micro level: Bake it down or delete it (Tool > Geometry > Micro) before changing subdivision levels";
        return false;
    }
    if (!subdivCommit(mesh)) {
        error = "The mesh topology changed, so its subdivision levels were dropped";
        return false;
    }
    const int n = int(mesh.multires->levels.size());
    if (level < 0 || level >= n) {
        error = "No subdivision level " + std::to_string(level + 1) + " (this Part has " + std::to_string(n) + ")";
        return false;
    }
    if (level == mesh.multires->current) return true;
    MultiresStack& s = mutableStack(mesh);
    for (int k = s.current + 1; k <= level; ++k)
        if (s.levels[size_t(k)].stale) evaluateLevel(s, k);
    const SubdivLevel leaving = s.levels[size_t(s.current)];
    s.current = level;
    enterLevel(mesh, level, bvh, &leaving);
    return true;
}

size_t subdivMaxTriangles() {
    size_t memory = 0;
#if defined(_WIN32)
    MEMORYSTATUSEX status{};
    status.dwLength = sizeof status;
    if (GlobalMemoryStatusEx(&status)) memory = size_t(status.ullTotalPhys);
#elif defined(_SC_PHYS_PAGES)
    const long pages = sysconf(_SC_PHYS_PAGES), page = sysconf(_SC_PAGESIZE);
    if (pages > 0 && page > 0) memory = size_t(pages) * size_t(page);
#endif
    return std::clamp<size_t>(memory / 10 * 6 / kDivideBytesPerTriangle, 50'000'000, 1'000'000'000);
}

bool subdivDivide(Mesh& mesh, bool smooth, std::string& error, BVH* bvh, size_t maxTriangles) {
    if (mesh.micro) {
        error = "This Part has a micro level: Bake it down or delete it (Tool > Geometry > Micro) before changing subdivision levels";
        return false;
    }
    if (maxTriangles == 0) maxTriangles = subdivMaxTriangles();
    if (mesh.triangleCount() == 0) {
        error = "Nothing to divide";
        return false;
    }
    if (mesh.multires) {
        if (!subdivCommit(mesh)) {
            // fall through: the stale stack was dropped, start a new one from this mesh
        } else if (mesh.multires->current != int(mesh.multires->levels.size()) - 1 &&
                   !subdivSetLevel(mesh, int(mesh.multires->levels.size()) - 1, error, bvh)) {
            return false;
        }
    }
    const bool cc = mesh.quadCount() > 0 || (mesh.multires && mesh.multires->levels.size() > 1 &&
                                             mesh.multires->levels.back().topo->catmullClark);
    // Projected size: Catmull-Clark makes 2n triangles per n-gon, Loop 4 per triangle.
    size_t projected = 0;
    if (cc) projected = mesh.quadCount() * 8 + (mesh.triangleCount() - 2 * mesh.quadCount()) * 6;
    else projected = mesh.triangleCount() * 4;
    if (projected > maxTriangles) {
        error = "Dividing would make " + std::to_string(projected) + " triangles (the limit for this computer's memory is " +
                std::to_string(maxTriangles) + ")";
        return false;
    }
    MultiresStack& s = ensureStack(mesh);
    const SubdivLevel leaving = s.levels.back();
    // The coarse level is the top one, which the working mesh is (with its edits folded in above).
    const Mesh& coarse = mesh;
    std::vector<uint32_t> pairing;
    if (cc) {
        pairing.resize(coarse.triangleCount());
        for (uint32_t t = 0; t < pairing.size(); ++t) pairing[t] = coarse.quadPartnerAt(t);
    }
    std::shared_ptr<SubdivTopology> tp = buildCoarse(coarse.triangles, uint32_t(coarse.vertexCount()), std::move(pairing), cc, smooth);
    tp->generated = true;
    SubdivLevel level;
    level.data = divideData(*tp, coarse);
    level.topo = tp;
    level.layerDetail.resize(coarse.layers.size());
    s.levels.push_back(std::move(level));
    s.current = int(s.levels.size()) - 1;
    enterLevel(mesh, s.current, bvh, &leaving);
    return true;
}

bool subdivDeleteLower(Mesh& mesh, std::string& error) {
    if (mesh.micro) {
        error = "This Part has a micro level: Bake it down or delete it (Tool > Geometry > Micro) before changing subdivision levels";
        return false;
    }
    if (!mesh.multires || !subdivCommit(mesh)) {
        error = "This Part has no subdivision levels";
        return false;
    }
    if (mesh.multires->current == 0) {
        error = "There are no lower levels (this is Level 1)";
        return false;
    }
    MultiresStack& s = mutableStack(mesh);
    if (generatedLevel(s.levels[size_t(s.current)])) { // the new base keeps its triangles itself
        Mesh& base = mutableData(s.levels[size_t(s.current)]);
        base.triangles = mesh.triangles;
        base.quadPartners = mesh.quadPartners;
    }
    s.levels.erase(s.levels.begin(), s.levels.begin() + s.current);
    s.current = 0;
    s.levels[0].topo.reset();
    s.levels[0].detail.reset();
    s.levels[0].layerDetail.clear();
    dropStackIfSingle(mesh);
    return true;
}

bool subdivDeleteHigher(Mesh& mesh, std::string& error) {
    if (!mesh.multires || !subdivCommit(mesh)) {
        error = "This Part has no subdivision levels";
        return false;
    }
    if (mesh.multires->current == int(mesh.multires->levels.size()) - 1) {
        error = "There are no higher levels (this is the highest)";
        return false;
    }
    MultiresStack& s = mutableStack(mesh);
    s.levels.resize(size_t(s.current) + 1);
    dropStackIfSingle(mesh);
    return true;
}

Mesh subdivLevelMesh(const Mesh& mesh, int level) {
    Mesh m = leanCopy(mesh);
    m.multires = mesh.multires;
    m.texture = mesh.texture;
    m.paintToTexture = mesh.paintToTexture;
    std::string error;
    if (!m.multires || level == subdivCurrentLevel(mesh) || !subdivSetLevel(m, level, error)) {
        m = leanCopy(mesh);
        m.texture = mesh.texture;
        m.paintToTexture = mesh.paintToTexture;
        m.rebuildTopology();
        m.recomputeAllNormals();
    }
    m.multires.reset();
    return m;
}

// --- Project files ---

std::shared_ptr<const SubdivTopology> rebuildSubdivTopology(const std::vector<glm::uvec3>& coarseTriangles,
                                                            uint32_t coarseVertices, uint32_t fineVertices,
                                                            const std::vector<glm::uvec3>* fineTriangles,
                                                            std::vector<uint32_t> pairing, bool catmullClark,
                                                            bool smooth, std::vector<uint32_t> vertexChild,
                                                            std::vector<uint32_t> edgeChild,
                                                            std::vector<uint32_t> faceChild, std::string& error) {
    std::shared_ptr<SubdivTopology> tp = buildCoarse(coarseTriangles, coarseVertices, std::move(pairing), catmullClark, smooth);
    if (tp->fineVertices != fineVertices) {
        error = "subdivision level vertex counts don't match";
        return nullptr;
    }
    if (!fineTriangles) {
        tp->generated = true;
        return tp;
    }
    tp->vertexChild = std::move(vertexChild);
    tp->edgeChild = std::move(edgeChild);
    tp->faceChild = std::move(faceChild);
    if (canonicalChildren(*tp) && matchesGenerated(*tp, *fineTriangles)) {
        markGenerated(*tp);
        return tp;
    }
    if (!buildFineMetadata(*tp, *fineTriangles, error)) return nullptr;
    return tp;
}

bool attachSubdivStack(Mesh& mesh, MultiresStack stack, std::string& error) {
    const size_t n = stack.levels.size();
    if (n < 2 || stack.current < 0 || size_t(stack.current) >= n) {
        error = "invalid subdivision levels";
        return false;
    }
    for (size_t j = 0; j < n; ++j) {
        SubdivLevel& l = stack.levels[j];
        if (l.data && generatedLevel(l)) { // the triangles and the generated quad pairs follow from the topology
            bool generatedPairs = l.topo->catmullClark && l.data->quadPartners.size() == l.topo->fineTriangles;
            for (size_t t = 0; t < l.data->quadPartners.size() && generatedPairs; ++t)
                generatedPairs = l.data->quadPartners[t] == uint32_t(t ^ 1);
            if (!l.data->triangles.empty() || generatedPairs) {
                if (l.data.use_count() > 1) l.data = std::make_shared<Mesh>(*l.data);
                std::vector<glm::uvec3>().swap(l.data->triangles);
                if (generatedPairs) std::vector<uint32_t>().swap(l.data->quadPartners);
            }
        }
        if (!l.data || (j > 0 && (!l.topo || l.topo->fineVertices != l.data->vertexCount() ||
                                  (!l.topo->generated && l.topo->fineTriangles != l.data->triangleCount()))) ||
            (l.detail && l.detail->size() != l.data->vertexCount())) {
            error = "subdivision level " + std::to_string(j + 1) + " doesn't fit the level below";
            return false;
        }
        for (const auto& d : l.layerDetail)
            if (d && d->size() != l.data->vertexCount()) {
                error = "subdivision level " + std::to_string(j + 1) + " has broken layer details";
                return false;
            }
        if (j <= size_t(stack.current) && l.stale) {
            error = "subdivision levels are out of date";
            return false;
        }
    }
    const SubdivLevel& cl = stack.levels[size_t(stack.current)];
    if (cl.data->vertexCount() != mesh.vertexCount() ||
        !(generatedLevel(cl) ? matchesGenerated(*cl.topo, mesh.triangles) : cl.data->triangles == mesh.triangles)) {
        error = "the current subdivision level doesn't match the mesh";
        return false;
    }
    mesh.multires = std::make_shared<MultiresStack>(std::move(stack));
    return true;
}

void convertWorldLayerDetail(MultiresStack& s) {
    bool any = false;
    for (const SubdivLevel& l : s.levels)
        for (const auto& d : l.layerDetail) any = any || bool(d);
    if (!any) return;
    for (size_t k = 1; k < s.levels.size(); ++k) {
        SubdivLevel& L = s.levels[k];
        if (!L.topo || !L.data) return;
        // The frames come from the level below, evaluated with its details (converted already).
        if (k >= 2 && s.levels[k - 1].stale) evaluateLevel(s, int(k) - 1);
        const SubdivTopology& tp = *L.topo;
        const std::vector<glm::vec3> Q = subdivideField(tp, tp.smooth, baseChannel(*s.levels[k - 1].data));
        std::vector<glm::vec3> n;
        std::vector<uint32_t> refs;
        levelFrames(L, Q, n, refs);
        for (auto& d : L.layerDetail) {
            if (!d || d->size() != Q.size()) continue;
            auto local = std::make_shared<std::vector<glm::vec3>>();
            layerDetailToLocal(refs, n, Q, *d, *local);
            d = std::move(local);
        }
    }
}

const Mesh& subdivLevelData(const Mesh& mesh, int level) { return *mesh.multires->levels[size_t(level)].data; }

const SubdivLevel& subdivLevel(const Mesh& mesh, int level) { return mesh.multires->levels[size_t(level)]; }

void subdivLevelFaces(const Mesh& mesh, int level, std::vector<glm::uvec3>& out) {
    const SubdivLevel& l = mesh.multires->levels[size_t(level)];
    if (generatedLevel(l)) generateFaces(*l.topo, out, nullptr);
    else out = l.data->triangles;
}

bool subdivInSync(const Mesh& mesh) {
    if (!mesh.multires) return true;
    const SubdivLevel& l = mesh.multires->levels[size_t(mesh.multires->current)];
    const Mesh& r = *l.data;
    return (generatedLevel(l) ? matchesGenerated(*l.topo, mesh.triangles) : sameArray(mesh.triangles, r.triangles)) &&
           !levelsDiffer(mesh, r);
}

// --- Rebuild Lower Levels ---

namespace {

struct Reconstruction {
    Mesh coarse;                                 // positions = the fine corner positions, attributes from the fine level
    std::vector<uint32_t> pairing;               // coarse quad pairs
    std::vector<uint32_t> vertexChild, faceChild; // fine vertex of each coarse vertex / polygon
    std::unordered_map<uint64_t, uint32_t> edgePoint; // coarse vertex pair -> fine edge vertex
    bool catmullClark = false;
};

uint64_t pairKey(uint32_t a, uint32_t b) { return a < b ? (uint64_t(a) << 32 | b) : (uint64_t(b) << 32 | a); }

enum Label : uint8_t { kUnset = 0, kO = 1, kE = 2, kF = 3 };

// All-quad mesh: label vertices O (original), E (edge) and F (face) so that every quad reads O, E, F, E.
bool reconstructCatmullClark(const Mesh& m, Reconstruction& out, std::string& error) {
    std::vector<uint32_t> pairing(m.triangleCount());
    for (uint32_t t = 0; t < pairing.size(); ++t) {
        pairing[t] = m.quadPartnerAt(t);
        if (pairing[t] == Mesh::kNoQuad) {
            error = "Reconstruct needs an all-quad mesh (or an all-triangle one)";
            return false;
        }
    }
    const std::shared_ptr<SubdivTopology> w = buildCoarse(m.triangles, uint32_t(m.vertexCount()), pairing, true, true);
    const size_t np = w->polygonCount();
    for (size_t p = 0; p < np; ++p)
        if (polySize(*w, p) != 4) {
            error = "Reconstruct needs an all-quad mesh";
            return false;
        }
    const uint32_t nv = uint32_t(m.vertexCount());
    std::vector<uint8_t> label(nv, kUnset), polyDone(np, 0);
    std::vector<uint32_t> touched, queue;
    // Vertices on a UV seam (corners with different UVs). A face point is inside one coarse face, so never on a
    // seam: on a regular closed grid (e.g. a torus) several readings fit, and the wrong ones split faces across UV
    // islands and UDIM tiles (#145).
    std::vector<uint8_t> seam(nv, 0);
    if (m.uvs.size() == m.triangles.size() * 3) {
        std::vector<glm::vec2> first(nv, glm::vec2(std::numeric_limits<float>::quiet_NaN()));
        for (size_t t = 0; t < m.triangles.size(); ++t)
            for (int c = 0; c < 3; ++c) {
                const uint32_t v = m.triangles[t][c];
                const glm::vec2 uv = m.uvs[t * 3 + size_t(c)];
                if (std::isnan(first[v].x)) first[v] = uv;
                else if (glm::any(glm::greaterThan(glm::abs(uv - first[v]), glm::vec2(1e-6f)))) seam[v] = 1;
            }
    }
    auto label4 = [&](uint32_t p, std::vector<uint8_t>& lab) -> int { // labels poly p from one known O/F corner
        const uint32_t o = w->polyOffsets[p];
        for (uint32_t k = 0; k < 4; ++k) {
            const uint8_t L = lab[w->polyVerts[o + k]];
            if (L != kO && L != kF) continue;
            const uint8_t want[4] = {L, kE, uint8_t(L == kO ? kF : kO), kE};
            for (uint32_t i = 0; i < 4; ++i) {
                const uint32_t v = w->polyVerts[o + (k + i) % 4];
                if (lab[v] == kUnset) {
                    lab[v] = want[i];
                    touched.push_back(v);
                } else if (lab[v] != want[i]) {
                    return -1;
                }
            }
            return 1;
        }
        return 0;
    };
    for (uint32_t seed = 0; seed < np; ++seed) {
        if (polyDone[seed]) continue;
        // Four ways to label the seed quad; keep the consistent one whose face points look most like quads.
        int best = -1;
        long bestScore = -1, bestSeams = 0, bestOdd = 0;
        std::vector<uint8_t> bestLabels;
        std::vector<uint32_t> bestPolys;
        for (int option = 0; option < 4; ++option) {
            std::vector<uint8_t> lab = label;
            touched.clear();
            const uint32_t o = w->polyOffsets[seed];
            lab[w->polyVerts[o + uint32_t(option / 2)]] = option % 2 ? kF : kO;
            if (label[w->polyVerts[o + uint32_t(option / 2)]] != kUnset) continue;
            touched.push_back(w->polyVerts[o + uint32_t(option / 2)]);
            std::vector<uint8_t> seen(np, 0);
            std::vector<uint32_t> polys;
            queue.assign(1, seed);
            seen[seed] = 1;
            bool ok = true;
            while (!queue.empty() && ok) {
                const uint32_t p = queue.back();
                queue.pop_back();
                if (label4(p, lab) != 1) {
                    ok = false;
                    break;
                }
                polys.push_back(p);
                for (uint32_t i = w->polyOffsets[p]; i < w->polyOffsets[p + 1]; ++i) {
                    const glm::uvec2 f = w->edgeFaces[w->polyEdges[i]];
                    for (uint32_t q : {f.x, f.y})
                        if (q != kNone && !seen[q]) {
                            seen[q] = 1;
                            queue.push_back(q);
                        }
                }
            }
            if (!ok) continue;
            // Face points of valence 4 (coarse quads) first, then off UV seams, then more quads. Seams only break
            // ties: a high-poly unwrapped on its own has seams through coarse faces too, and the reading with the
            // corners as face points (all of valence 3 or 5) put fewer face points on them (#145).
            long score = 0, seams = 0, odd = 0;
            for (uint32_t v : touched) {
                if (lab[v] == kO) continue;
                bool border = false;
                for (uint32_t i = w->vertEdgeOffsets[v]; i < w->vertEdgeOffsets[v + 1]; ++i)
                    border = border || w->edgeFaces[w->vertEdges[i]].y == kNone;
                const uint32_t valence = w->vertEdgeOffsets[v + 1] - w->vertEdgeOffsets[v];
                if (lab[v] == kE) { // an edge point joins its two corners and two face points (one on a border)
                    ok = ok && valence == (border ? 3u : 4u);
                    continue;
                }
                seams += seam[v];
                // A face point is never on a border (on an open mesh, e.g. a UDIM plane, the swapped
                // reading has more face points: #145) and is in a triangle or a quad.
                ok = ok && !border && (valence == 3 || valence == 4);
                const bool quad = valence == 4;
                score += quad ? 2 : 1;
                odd += !quad;
            }
            if (!ok) continue;
            if (best < 0 || odd < bestOdd || (odd == bestOdd && (seams < bestSeams || (seams == bestSeams && score > bestScore)))) {
                best = option;
                bestScore = score;
                bestSeams = seams;
                bestOdd = odd;
                bestLabels = std::move(lab);
                bestPolys = std::move(polys);
            }
        }
        if (best < 0) {
            error = "The mesh is not a regular Catmull-Clark subdivision (no consistent corner / edge / face pattern)";
            return false;
        }
        label = std::move(bestLabels);
        for (uint32_t p : bestPolys) polyDone[p] = 1;
    }
    // Coarse vertices: the O vertices in index order.
    std::vector<uint32_t> coarseIndex(nv, kNone);
    for (uint32_t v = 0; v < nv; ++v) {
        if (label[v] == kUnset) {
            error = "The mesh has loose vertices";
            return false;
        }
        if (label[v] == kO) {
            coarseIndex[v] = uint32_t(out.vertexChild.size());
            out.vertexChild.push_back(v);
        }
    }
    // Quads around each F vertex: (O, e_i, F, e_{i-1}); walk them in order to get the coarse polygon.
    std::vector<uint32_t> fquads; // per poly: index of its F corner
    std::vector<std::vector<uint32_t>> around(nv);
    for (uint32_t p = 0; p < np; ++p) {
        const uint32_t o = w->polyOffsets[p];
        for (uint32_t k = 0; k < 4; ++k)
            if (label[w->polyVerts[o + k]] == kF) around[w->polyVerts[o + k]].push_back(p * 4 + k);
    }
    out.catmullClark = true;
    for (uint32_t f = 0; f < nv; ++f) {
        if (label[f] != kF) continue;
        const auto& qs = around[f];
        if (qs.size() < 3 || qs.size() > 4) {
            error = "The mesh is not a regular subdivision (a face point joins " + std::to_string(qs.size()) + " quads)";
            return false;
        }
        auto at = [&](uint32_t q, uint32_t d) { return w->polyVerts[w->polyOffsets[q / 4] + (q % 4 + d) % 4]; };
        std::vector<uint32_t> corners, edgesPts;
        uint32_t q = qs[0];
        for (size_t step = 0; step < qs.size(); ++step) {
            corners.push_back(at(q, 2));      // O
            edgesPts.push_back(at(q, 3));     // e_i, towards the next corner
            const uint32_t next = at(q, 3);
            uint32_t found = kNone;
            for (uint32_t r : qs)
                if (at(r, 1) == next) found = r;
            if (found == kNone) {
                error = "The mesh is not a regular subdivision (open face fan)";
                return false;
            }
            q = found;
        }
        if (q != qs[0]) {
            error = "The mesh is not a regular subdivision (face fan does not close)";
            return false;
        }
        const size_t n = corners.size();
        const uint32_t firstTri = uint32_t(out.coarse.triangles.size());
        for (size_t i = 0; i < n; ++i) {
            const uint32_t a = coarseIndex[corners[i]], b = coarseIndex[corners[(i + 1) % n]];
            auto [it, inserted] = out.edgePoint.try_emplace(pairKey(a, b), edgesPts[i]);
            if (!inserted && it->second != edgesPts[i]) {
                error = "The mesh is not a regular subdivision (edge points disagree)";
                return false;
            }
        }
        if (n == 4) {
            out.coarse.triangles.push_back({coarseIndex[corners[0]], coarseIndex[corners[1]], coarseIndex[corners[2]]});
            out.coarse.triangles.push_back({coarseIndex[corners[0]], coarseIndex[corners[2]], coarseIndex[corners[3]]});
            out.pairing.push_back(firstTri + 1);
            out.pairing.push_back(firstTri);
        } else {
            out.coarse.triangles.push_back({coarseIndex[corners[0]], coarseIndex[corners[1]], coarseIndex[corners[2]]});
            out.pairing.push_back(kNone);
        }
        out.faceChild.push_back(f);
    }
    return true;
}

// All-triangle mesh: label vertices O / E so every triangle is a corner (O, E, E) or a centre (E, E, E) one.
bool reconstructLoop(const Mesh& m, Reconstruction& out, std::string& error) {
    const std::shared_ptr<SubdivTopology> w = buildCoarse(m.triangles, uint32_t(m.vertexCount()), {}, false, true);
    const uint32_t nv = uint32_t(m.vertexCount()), nt = uint32_t(m.triangleCount());
    std::vector<uint8_t> label(nv, kUnset), type(nt, 0), done(nt, 0); // type 1 = corner, 2 = centre
    for (uint32_t seed = 0; seed < nt; ++seed) {
        if (done[seed]) continue;
        bool solved = false;
        for (int option = 0; option < 4 && !solved; ++option) {
            std::vector<uint8_t> lab = label, ty = type;
            const glm::uvec3& st = m.triangles[seed];
            bool ok = true;
            for (int c = 0; c < 3; ++c) {
                const uint8_t want = option == c ? kO : kE;
                if (lab[st[c]] != kUnset && lab[st[c]] != want) ok = false;
                lab[st[c]] = want;
            }
            ty[seed] = option < 3 ? 1 : 2;
            std::vector<uint32_t> queue{seed}, comp;
            std::vector<uint8_t> seen(nt, 0);
            seen[seed] = 1;
            while (!queue.empty() && ok) {
                const uint32_t t = queue.back();
                queue.pop_back();
                comp.push_back(t);
                const glm::uvec3& tri = m.triangles[t];
                for (uint32_t i = w->polyOffsets[t]; i < w->polyOffsets[t + 1] && ok; ++i) {
                    const glm::uvec2 ef = w->edgeFaces[w->polyEdges[i]];
                    const uint32_t q = ef.x == t ? ef.y : ef.x;
                    if (q == kNone) continue;
                    const glm::uvec2 ed = w->edges[w->polyEdges[i]];
                    const uint8_t la = lab[ed.x], lb = lab[ed.y];
                    const glm::uvec3& qt = m.triangles[q];
                    uint32_t third = qt.x;
                    for (int c = 0; c < 3; ++c)
                        if (qt[c] != ed.x && qt[c] != ed.y) third = qt[c];
                    uint8_t qtype, thirdLabel;
                    if (la == kO || lb == kO) {
                        qtype = 1;
                        thirdLabel = kE;
                    } else {
                        qtype = ty[t] == 1 ? 2 : 1;
                        thirdLabel = qtype == 1 ? kO : kE;
                    }
                    (void)tri;
                    if (ty[q] && ty[q] != qtype) ok = false;
                    ty[q] = qtype;
                    if (lab[third] != kUnset && lab[third] != thirdLabel) ok = false;
                    lab[third] = thirdLabel;
                    if (!seen[q]) {
                        seen[q] = 1;
                        queue.push_back(q);
                    }
                }
            }
            if (!ok) continue;
            label = std::move(lab);
            type = std::move(ty);
            for (uint32_t t : comp) done[t] = 1;
            solved = true;
        }
        if (!solved) {
            error = "The mesh is not a regular Loop subdivision (no consistent corner / edge pattern)";
            return false;
        }
    }
    std::vector<uint32_t> coarseIndex(nv, kNone);
    for (uint32_t v = 0; v < nv; ++v) {
        if (label[v] == kUnset) {
            error = "The mesh has loose vertices";
            return false;
        }
        if (label[v] == kO) {
            coarseIndex[v] = uint32_t(out.vertexChild.size());
            out.vertexChild.push_back(v);
        }
    }
    // The two O neighbours of every E vertex (from the corner triangles).
    std::vector<glm::uvec2> ends(nv, glm::uvec2(kNone));
    auto addEnd = [&](uint32_t e, uint32_t o) {
        if (ends[e].x == o || ends[e].y == o) return true;
        if (ends[e].x == kNone) ends[e].x = o;
        else if (ends[e].y == kNone) ends[e].y = o;
        else return false;
        return true;
    };
    for (uint32_t t = 0; t < nt; ++t) {
        if (type[t] != 1) continue;
        const glm::uvec3& tri = m.triangles[t];
        for (int c = 0; c < 3; ++c)
            if (label[tri[c]] == kO && (!addEnd(tri[(c + 1) % 3], tri[c]) || !addEnd(tri[(c + 2) % 3], tri[c]))) {
                error = "The mesh is not a regular subdivision (an edge point has more than two ends)";
                return false;
            }
    }
    for (uint32_t t = 0; t < nt; ++t) {
        if (type[t] != 2) continue;
        const glm::uvec3& e = m.triangles[t];
        auto common = [&](uint32_t a, uint32_t b) {
            for (uint32_t x : {ends[a].x, ends[a].y})
                if (x != kNone && (x == ends[b].x || x == ends[b].y)) return x;
            return kNone;
        };
        const uint32_t c1 = common(e[0], e[1]), c2 = common(e[1], e[2]), c0 = common(e[2], e[0]);
        if (c0 == kNone || c1 == kNone || c2 == kNone) {
            error = "The mesh is not a regular subdivision (a centre triangle has no corners)";
            return false;
        }
        const uint32_t a = coarseIndex[c0], b = coarseIndex[c1], c = coarseIndex[c2];
        const uint32_t pts[3] = {e[0], e[1], e[2]};
        const uint64_t keys[3] = {pairKey(a, b), pairKey(b, c), pairKey(c, a)};
        for (int i = 0; i < 3; ++i) {
            auto [it, inserted] = out.edgePoint.try_emplace(keys[i], pts[i]);
            if (!inserted && it->second != pts[i]) {
                error = "The mesh is not a regular subdivision (edge points disagree)";
                return false;
            }
        }
        out.coarse.triangles.push_back({a, b, c});
    }
    return true;
}

} // namespace

bool subdivReconstruct(Mesh& mesh, std::string& error, BVH* bvh) {
    if (mesh.micro) {
        error = "This Part has a micro level: Bake it down or delete it (Tool > Geometry > Micro) before changing subdivision levels";
        return false;
    }
    if (mesh.multires) {
        if (!subdivCommit(mesh)) {
            // dropped: reconstruct from this mesh alone
        } else if (mesh.multires->current != 0) {
            error = "Rebuild Lower Levels works at the lowest level (step down to Level 1 first)";
            return false;
        }
    }
    if (mesh.triangleCount() == 0) {
        error = "Nothing to reconstruct";
        return false;
    }
    Reconstruction rec;
    const bool quads = mesh.quadCount() > 0;
    if (!(quads ? reconstructCatmullClark(mesh, rec, error) : reconstructLoop(mesh, rec, error))) return false;
    const uint32_t nc = uint32_t(rec.vertexChild.size());
    if (nc < 3 || rec.coarse.triangles.empty()) {
        error = "The mesh is too small to have a lower level";
        return false;
    }
    Mesh& coarse = rec.coarse;
    coarse.positions.resize(nc);
    for (uint32_t v = 0; v < nc; ++v) coarse.positions[v] = mesh.positions[rec.vertexChild[v]];
    std::shared_ptr<SubdivTopology> tp = buildCoarse(coarse.triangles, nc, rec.pairing, rec.catmullClark, true);
    tp->vertexChild = rec.vertexChild;
    tp->faceChild = rec.catmullClark ? rec.faceChild : std::vector<uint32_t>{};
    tp->edgeChild.resize(tp->edges.size());
    for (size_t e = 0; e < tp->edges.size(); ++e) {
        auto it = rec.edgePoint.find(pairKey(tp->edges[e].x, tp->edges[e].y));
        if (it == rec.edgePoint.end()) {
            error = "The mesh is not a regular subdivision (an edge has no edge point)";
            return false;
        }
        tp->edgeChild[e] = it->second;
    }
    if (tp->fineVertices != mesh.vertexCount()) {
        error = "The mesh is not a regular subdivision (vertex counts don't add up)";
        return false;
    }
    if (!buildFineMetadata(*tp, mesh.triangles, error)) return false;
    // Expected fine triangle count: 2n per n-gon (Catmull-Clark) or 4 per triangle (Loop).
    size_t expected = 0;
    for (size_t p = 0; p < tp->polygonCount(); ++p) expected += tp->catmullClark ? 2 * polySize(*tp, p) : 4;
    if (expected != mesh.triangleCount()) {
        error = "The mesh is not a regular subdivision (triangle counts don't add up)";
        return false;
    }

    // Coarse shape: the fine level's corner vertices (fitting the cage so its subdivision passes
    // through them overshoots badly on sharp shapes, and compounds over several levels); the detail of the fine
    // level keeps it exactly as it was.
    const std::vector<glm::vec3>& fineBase = baseChannel(mesh);
    for (uint32_t v = 0; v < nc; ++v) coarse.positions[v] = fineBase[rec.vertexChild[v]];
    // Attributes: everything copied down from the fine level.
    std::vector<uint8_t> f;
    if (mesh.hasMask()) restrictVertices(*tp, mesh.mask, coarse.mask, 0.0f, nullptr, f);
    if (mesh.hasColors()) restrictVertices(*tp, mesh.colors, coarse.colors, glm::vec3(1.0f), nullptr, f);
    if (mesh.hasFaceGroups()) restrictFaces(*tp, mesh.facegroups, coarse.facegroups, coarse.triangleCount(), 0u, nullptr, f);
    if (mesh.hasHidden()) restrictFaces(*tp, mesh.hidden, coarse.hidden, coarse.triangleCount(), uint8_t(0), nullptr, f);
    if (mesh.hasUvs()) restrictUvs(*tp, coarse.triangles, mesh.uvs, coarse.uvs, nullptr, f);
    if (!rec.pairing.empty()) coarse.quadPartners = rec.pairing;
    if (!mesh.paintLayers.empty()) {
        restrictVertices(*tp, mesh.paintBase, coarse.paintBase, glm::vec3(1.0f), nullptr, f);
        for (const PaintLayer& l : mesh.paintLayers) {
            PaintLayer nl = l;
            nl.color.clear();
            nl.alpha.clear();
            restrictVertices(*tp, l.color, nl.color, glm::vec3(1.0f), nullptr, f);
            restrictVertices(*tp, l.alpha, nl.alpha, 0.0f, nullptr, f);
            coarse.paintLayers.push_back(std::move(nl));
        }
        coarse.activePaintLayer = mesh.activePaintLayer;
        compositePaintAll(coarse);
    }
    SubdivLevel fineLevel;
    fineLevel.topo = tp;
    if (!mesh.layers.empty()) {
        // The coarse base is the positions so far (the layers' offsets are added below).
        const std::vector<glm::vec3> Q = subdivideField(*tp, true, coarse.positions);
        coarse.base = coarse.positions;
        const std::vector<glm::vec3> n = fineNormals(mesh.triangles, Q);
        const std::vector<uint32_t> refs = frameRefs(tp->fineVertices, mesh.triangles);
        for (const SculptLayer& l : mesh.layers) {
            SculptLayer cl{l.name, std::vector<glm::vec3>(nc), l.weight};
            for (uint32_t v = 0; v < nc; ++v) cl.delta[v] = l.delta[rec.vertexChild[v]];
            const std::vector<glm::vec3> s = subdivideField(*tp, true, cl.delta);
            std::vector<glm::vec3> world(s.size());
            for (size_t v = 0; v < s.size(); ++v) world[v] = l.delta[v] - s[v];
            auto d = std::make_shared<std::vector<glm::vec3>>();
            layerDetailToLocal(refs, n, Q, world, *d);
            fineLevel.layerDetail.push_back(std::move(d));
            coarse.layers.push_back(std::move(cl));
        }
        evaluateLayers(coarse);
    }
    // The fine level's detail is what fits its positions (fitted when the coarse level changes; SubdivLevel::detail).
    MultiresStack& s = ensureStack(mesh);
    fineLevel.data = s.levels[0].data;
    fineLevel.stale = false;
    s.levels[0] = std::move(fineLevel);
    s.levels.insert(s.levels.begin(), SubdivLevel{std::make_shared<Mesh>(std::move(coarse)), nullptr, nullptr, {}, false});
    s.current = 0;
    enterLevel(mesh, 0, bvh, &s.levels[1]);
    return true;
}

// --- Undo ---

size_t SubdivUndo::bytes() const {
    // Only what this record alone keeps alive (shared levels are counted by whoever else holds them).
    if (!stack) return plain && plain.use_count() == 1 ? plain->positions.size() * 64 : 0;
    size_t total = 0;
    for (const SubdivLevel& l : stack->levels) {
        if (l.data && l.data.use_count() == 1) total += l.data->positions.size() * 40 + l.data->triangles.size() * 20;
        if (l.detail && l.detail.use_count() == 1) total += l.detail->size() * sizeof(glm::vec3);
    }
    return total;
}

void applySubdivUndo(SubdivUndo& r, Mesh& mesh, BVH& bvh) {
    subdivCommit(mesh);
    const SubdivLevel leaving = mesh.multires ? mesh.multires->levels[size_t(mesh.multires->current)] : SubdivLevel{};
    std::shared_ptr<SubdivLevelCache> cache = mesh.multires ? mesh.multires->cache : nullptr;
    std::swap(mesh.multires, r.stack);
    if (mesh.multires) {
        if (!mesh.multires->cache) mesh.multires->cache = std::move(cache);
        enterLevel(mesh, mesh.multires->current, &bvh, &leaving);
        return;
    } else if (r.plain) {
        std::shared_ptr<PaintTexture> texture = mesh.texture;
        std::shared_ptr<const SelectionSetList> selectionSets = mesh.selectionSets;
        const bool toTexture = mesh.paintToTexture;
        mesh = leanCopy(*r.plain);
        mesh.texture = std::move(texture);
        mesh.selectionSets = std::move(selectionSets);
        mesh.paintToTexture = toTexture;
        mesh.rebuildTopology();
        mesh.recomputeAllNormals();
        if (hasPaintLayers(mesh)) compositePaintAll(mesh);
    }
    mesh.topologyDirty = true;
    bvh.build(mesh);
}

namespace {

// Runs a level operation on the active Part as one undo step that swaps the level stack back.
// `plainLevel`: for operations that can start without levels, the level of the new stack that holds the mesh
// as it was (it is the undo's `plain` mesh, shared rather than copied).
template <class Op>
bool runUndoable(Document& doc, const std::string& label, Op op, std::string& message, int plainLevel = -1) {
    Mesh& mesh = doc.mesh;
    subdivCommit(mesh);
    auto rec = std::make_unique<SubdivUndo>();
    rec->stack = mesh.multires; // holding it makes the operation copy what it changes
    const bool hadStack = bool(rec->stack);
    const int fromLevel = subdivCurrentLevel(mesh);
    if (!hadStack && plainLevel < 0) return false;
    if (!op(mesh, message, &doc.bvh)) return false;
    if (!hadStack) rec->plain = mesh.multires->levels[size_t(plainLevel)].data;
    else if (!mesh.multires) rec->plain = rec->stack->levels[size_t(fromLevel)].data; // the level that remained
    doc.bvhDirty = false;
    UndoRecord r;
    r.label = label;
    r.subdiv = std::move(rec);
    doc.undo.push(std::move(r));
    if (doc.activeLayer >= int(mesh.layers.size())) doc.activeLayer = -1;
    return true;
}

std::string levelSummary(const Mesh& m) {
    std::string text = subdivLevelText(m);
    return (text.empty() ? std::string("No subdivision levels") : text) + ", " + std::to_string(m.triangleCount()) + " triangles";
}

} // namespace

bool divideUndoable(Document& doc, bool smooth, std::string& message) {
    return runUndoable(doc, "Add Level", [&](Mesh& m, std::string& msg, BVH* bvh) {
        if (!subdivDivide(m, smooth, msg, bvh)) return false;
        msg = "Added a level: " + levelSummary(m);
        return true;
    }, message, doc.mesh.multires ? -1 : 0);
}

bool setSubdivLevelUndoable(Document& doc, int level, std::string& message) {
    if (!doc.mesh.multires) {
        message = "This Part has no subdivision levels (Divide adds them)";
        return false;
    }
    if (level == subdivCurrentLevel(doc.mesh)) {
        message = levelSummary(doc.mesh);
        return true;
    }
    return runUndoable(doc, "Level " + std::to_string(level + 1), [&](Mesh& m, std::string& msg, BVH* bvh) {
        if (!subdivSetLevel(m, level, msg, bvh)) return false;
        msg = levelSummary(m);
        return true;
    }, message);
}

bool deleteLowerUndoable(Document& doc, std::string& message) {
    return runUndoable(doc, "Remove Below", [&](Mesh& m, std::string& msg, BVH*) {
        if (!subdivDeleteLower(m, msg)) return false;
        msg = "Deleted the lower levels: " + levelSummary(m);
        return true;
    }, message);
}

bool deleteHigherUndoable(Document& doc, std::string& message) {
    return runUndoable(doc, "Remove Above", [&](Mesh& m, std::string& msg, BVH*) {
        if (!subdivDeleteHigher(m, msg)) return false;
        msg = "Deleted the higher levels: " + levelSummary(m);
        return true;
    }, message);
}

bool freezeLevelsUndoable(Document& doc, std::string& message) {
    if (!doc.mesh.multires) {
        message = "This Part has no subdivision levels";
        return false;
    }
    const int level = subdivCurrentLevel(doc.mesh) + 1, levels = subdivLevelCount(doc.mesh);
    return runUndoable(doc, "Freeze Levels", [&](Mesh& m, std::string& msg, BVH*) {
        if (m.micro) {
            msg = "This Part has a micro level: Bake it down or delete it (Tool > Geometry > Micro) before changing subdivision levels";
            return false;
        }
        if (m.multires && m.multires->current + 1 < int(m.multires->levels.size()) && !subdivDeleteHigher(m, msg)) return false;
        if (m.multires && m.multires->current > 0 && !subdivDeleteLower(m, msg)) return false;
        msg = "Froze Level " + std::to_string(level) + " of " + std::to_string(levels) + ": " + levelSummary(m);
        return true;
    }, message);
}

bool reconstructUndoable(Document& doc, std::string& message) {
    return runUndoable(doc, "Rebuild Lower Levels", [&](Mesh& m, std::string& msg, BVH* bvh) {
        if (!subdivReconstruct(m, msg, bvh)) return false;
        msg = "Reconstructed a lower level: " + levelSummary(m);
        return true;
    }, message, doc.mesh.multires ? -1 : 1);
}

// --- Moving values between levels (Selection Sets, core/SelectionSets.h) ---

namespace {

bool mapLevelsValid(const Mesh& mesh, int from, int to) {
    const int n = subdivLevelCount(mesh);
    return n > 0 && from >= 0 && to >= 0 && from < n && to < n;
}

template <class T>
bool mapVertexValues(const Mesh& mesh, int from, int to, std::vector<T>& values, T fill, bool smooth) {
    if (from == to) return true;
    if (!mapLevelsValid(mesh, from, to)) return false;
    const MultiresStack& s = *mesh.multires;
    std::vector<T> next;
    std::vector<uint8_t> flags;
    for (int k = from; k > to; --k) { // down: each coarse vertex takes its child's value
        const SubdivTopology& tp = *s.levels[size_t(k)].topo;
        if (values.size() != tp.fineVertices) values.assign(tp.fineVertices, fill);
        next.clear();
        restrictVertices(tp, values, next, fill, nullptr, flags);
        values.swap(next);
    }
    for (int k = from + 1; k <= to; ++k) { // up: interpolated (or through the level's stencils)
        const SubdivTopology& tp = *s.levels[size_t(k)].topo;
        if (values.size() != tp.coarseVertices) values.assign(tp.coarseVertices, fill);
        next.clear();
        if (smooth) next = subdivideField(tp, tp.smooth, values);
        else prolongVertices(tp, values, next, fill, nullptr, flags);
        values.swap(next);
    }
    return true;
}

template <class T>
bool mapTriangleValues(const Mesh& mesh, int from, int to, std::vector<T>& values, T fill) {
    if (from == to) return true;
    if (!mapLevelsValid(mesh, from, to)) return false;
    const MultiresStack& s = *mesh.multires;
    std::vector<T> next;
    std::vector<uint8_t> flags;
    for (int k = from; k > to; --k) {
        const SubdivTopology& tp = *s.levels[size_t(k)].topo;
        if (values.size() != tp.fineTriangles) values.assign(tp.fineTriangles, fill);
        next.clear();
        restrictFaces(tp, values, next, s.levels[size_t(k) - 1].triangleCount(), fill, nullptr, flags);
        values.swap(next);
    }
    for (int k = from + 1; k <= to; ++k) {
        const SubdivTopology& tp = *s.levels[size_t(k)].topo;
        if (values.size() != s.levels[size_t(k) - 1].triangleCount()) values.assign(s.levels[size_t(k) - 1].triangleCount(), fill);
        next.clear();
        prolongFaces(tp, values, next, fill, nullptr, flags);
        values.swap(next);
    }
    return true;
}

} // namespace

bool subdivMapVertices(const Mesh& mesh, int from, int to, std::vector<float>& values) {
    return mapVertexValues(mesh, from, to, values, 0.0f, false);
}
bool subdivMapVertices(const Mesh& mesh, int from, int to, std::vector<glm::vec3>& values, glm::vec3 fill, bool smooth) {
    return mapVertexValues(mesh, from, to, values, fill, smooth);
}
bool subdivMapTriangles(const Mesh& mesh, int from, int to, std::vector<uint32_t>& values) {
    return mapTriangleValues(mesh, from, to, values, 0u);
}
bool subdivMapTriangles(const Mesh& mesh, int from, int to, std::vector<uint8_t>& values) {
    return mapTriangleValues(mesh, from, to, values, uint8_t(0));
}
bool subdivMapCorners(const Mesh& mesh, int from, int to, std::vector<glm::vec2>& values) {
    if (from == to) return true;
    if (!mapLevelsValid(mesh, from, to)) return false;
    const MultiresStack& s = *mesh.multires;
    std::vector<glm::vec2> next;
    std::vector<uint8_t> flags;
    std::vector<glm::uvec3> coarseTris;
    for (int k = from; k > to; --k) {
        const SubdivTopology& tp = *s.levels[size_t(k)].topo;
        if (values.size() != tp.fineTriangles * 3) values.assign(tp.fineTriangles * 3, glm::vec2(0.0f));
        subdivLevelFaces(mesh, k - 1, coarseTris);
        next.clear();
        restrictUvs(tp, coarseTris, values, next, nullptr, flags);
        values.swap(next);
    }
    for (int k = from + 1; k <= to; ++k) {
        const SubdivTopology& tp = *s.levels[size_t(k)].topo;
        const size_t coarse = s.levels[size_t(k) - 1].triangleCount() * 3;
        if (values.size() != coarse) values.assign(coarse, glm::vec2(0.0f));
        next.clear();
        prolongUvs(tp, values, next, nullptr, flags);
        values.swap(next);
    }
    return true;
}

} // namespace sf