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.

61.1 KB
Raw Blame
// SculptForge - open source digital sculpting
// SPDX-License-Identifier: GPL-3.0-or-later
//
// Micro-displacement levels (core/Micro.h): the data, evaluation, Divide / Delete, picking, the renderer's
// shading, baking down and displacement maps. The brushes are in MicroSculpt.cpp, the commands in
// MicroCommands.cpp.
#include "core/Micro.h"
#include "core/FocusDetail.h"

#include "core/BakeImage.h"
#include "core/BVH.h"
#include "core/Multires.h"
#include "core/ThreadPool.h"
#include "core/TierConfig.h"

#include <algorithm>
#include <atomic>
#include <bit>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <limits>
#include <mutex>

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

namespace sf {

// ---------------------------------------------------------------------------
// MicroMesh
// ---------------------------------------------------------------------------

uint64_t MicroMesh::newSerial() {
    static std::atomic<uint64_t> next{1};
    return next++;
}

size_t MicroMesh::microVertices() const {
    size_t edges = size_t(baseTriangles) * 3 / 2;
    if (edgeNeighbor.size() == size_t(baseTriangles) * 3) {
        size_t boundary = 0;
        for (uint32_t e : edgeNeighbor) boundary += e == kNone;
        edges = (size_t(baseTriangles) * 3 + boundary) / 2;
    }
    const size_t interior = n >= 2 ? size_t(n - 1) * (n - 2) / 2 : 0;
    return size_t(baseVertices) + edges * (n - 1) + size_t(baseTriangles) * interior;
}

size_t MicroMesh::bytes() const {
    return disp.capacity() * sizeof(int16_t) + mask.capacity() + triRange.capacity() * sizeof(uint16_t) +
           edgeNeighbor.capacity() * sizeof(uint32_t) + dirtyBits.capacity() * sizeof(uint64_t);
}

void MicroMesh::clearDirty() {
    std::fill(dirtyBits.begin(), dirtyBits.end(), 0);
    allDirty = false;
    maskDirty = false;
    rescaled = false;
}

int MicroMesh::widen(float need) {
    if (!(need > rangeWorld())) return 1;
    int doublings = 2;
    while (need > 32767.0f * step * float(1 << doublings) && doublings < 12) ++doublings;
    const int div = 1 << doublings;
    poolFor(disp.size(), [&](size_t b, size_t e) {
        for (size_t i = b; i < e; ++i) disp[i] = int16_t(int(disp[i]) / div);
    }, 1 << 16);
    for (uint16_t& v : triRange) v = uint16_t(std::min(int(v) / div + 1, 32767));
    rangeMax = uint16_t(std::min(int(rangeMax) / div + 1, 32767));
    step *= float(div);
    rescaled = true;
    reach.all = true;
    if (focus) focus->rescale(*this, doublings); // (the tiles not in disp: core/FocusDetail.h)
    ++revision;
    return div;
}

void MicroMesh::ensureTopology(const Mesh& base) {
    const size_t nt = base.triangleCount();
    if (edgeNeighbor.size() == nt * 3 && nt == baseTriangles) return;
    edgeNeighbor.assign(nt * 3, kNone);
    poolFor(nt, [&](size_t b, size_t e) {
        for (size_t t = b; t < e; ++t) {
            const glm::uvec3 tri = base.triangles[t];
            for (int k = 0; k < 3; ++k) {
                const uint32_t a = tri[k], c = tri[(k + 1) % 3];
                for (uint32_t u : base.vertexTriangles(a)) {
                    if (u == t) continue;
                    const glm::uvec3 o = base.triangles[u];
                    int f = -1;
                    for (int q = 0; q < 3 && f < 0; ++q)
                        if ((o[q] == a && o[(q + 1) % 3] == c) || (o[q] == c && o[(q + 1) % 3] == a)) f = q;
                    if (f >= 0) {
                        edgeNeighbor[t * 3 + size_t(k)] = (u << 2) | uint32_t(f);
                        break;
                    }
                }
            }
        }
    }, 1 << 12);
}

// ---------------------------------------------------------------------------
// Evaluation
// ---------------------------------------------------------------------------

void MicroTriangle::set(const Mesh& base, uint32_t tri, uint32_t segments) {
    const glm::uvec3 t = base.triangles[tri];
    uint8_t o[3] = {0, 1, 2};
    if (t[o[0]] > t[o[1]]) std::swap(o[0], o[1]);
    if (t[o[1]] > t[o[2]]) std::swap(o[1], o[2]);
    if (t[o[0]] > t[o[1]]) std::swap(o[0], o[1]);
    for (int k = 0; k < 3; ++k) {
        slot[k] = o[k];
        p[k] = base.positions[t[o[k]]];
        nrm[k] = base.normals[t[o[k]]];
    }
    n = segments;
    invN = 1.0f / float(segments);
}

// The same operations, in the same order, as the renderer's vertex shader (render/MicroRenderer.cpp): corners in
// ascending vertex order, so a point on a shared edge (whose third weight is exactly 0) comes out bit-identical
// from both triangles.
void MicroTriangle::evalWeights(const float wc[3], glm::vec3& surface, glm::vec3& normal) const {
    const float w0 = wc[slot[0]], w1 = wc[slot[1]], w2 = wc[slot[2]];
    glm::vec3 f = p[0] * w0;
    f += p[1] * w1;
    f += p[2] * w2;
    glm::vec3 nn = nrm[0] * w0;
    nn += nrm[1] * w1;
    nn += nrm[2] * w2;
    // Phong tessellation: the flat point pulled towards each corner's tangent plane.
    glm::vec3 pull = nrm[0] * (w0 * glm::dot(f - p[0], nrm[0]));
    pull += nrm[1] * (w1 * glm::dot(f - p[1], nrm[1]));
    pull += nrm[2] * (w2 * glm::dot(f - p[2], nrm[2]));
    surface = f - pull * MicroMesh::kPhong;
    const float len = glm::length(nn);
    normal = len > 1e-20f ? nn / len : glm::vec3(0.0f, 0.0f, 1.0f);
}

void MicroTriangle::eval(uint32_t i, uint32_t j, glm::vec3& surface, glm::vec3& normal) const {
    const float w[3] = {float(n - i - j) * invN, float(i) * invN, float(j) * invN};
    evalWeights(w, surface, normal);
}

glm::vec3 MicroTriangle::flat(uint32_t i, uint32_t j) const {
    const float wc[3] = {float(n - i - j) * invN, float(i) * invN, float(j) * invN};
    glm::vec3 f = p[0] * wc[slot[0]];
    f += p[1] * wc[slot[1]];
    f += p[2] * wc[slot[2]];
    return f;
}

MicroPatch microPatch(Mesh& m, uint32_t id) {
    MicroMesh& mm = mutableMicro(m);
    MicroPatch p;
    p.id = id;
    p.n = mm.n;
    p.heights = mm.disp.data() + size_t(id) * mm.samples;
    p.mask = mm.hasMask() ? mm.mask.data() + size_t(id) * mm.samples : nullptr;
    return p;
}

bool PatchPageTable::resident(uint32_t patch) const {
    if (!mm_.disp.mapped()) return true;
    return mm_.disp.rangeResident(size_t(patch) * mm_.samples, mm_.samples);
}

size_t PatchPageTable::residentPatches() const {
    if (!mm_.disp.mapped()) return mm_.baseTriangles;
    size_t count = 0;
    for (uint32_t t = 0; t < mm_.baseTriangles; ++t) count += resident(t);
    return count;
}

int microLevel(const Mesh& m) { return m.micro ? m.micro->level : 0; }
size_t microTriangleCount(const Mesh& m) { return m.micro ? m.micro->microTriangles() : 0; }
size_t microBytes(const Mesh& m) { return m.micro ? m.micro->bytes() : 0; }

std::string microText(const Mesh& m) {
    if (!m.micro) return {};
    char buf[64];
    std::snprintf(buf, sizeof buf, "Micro %d (%.1fM)", m.micro->level, double(m.micro->microTriangles()) / 1e6);
    return buf;
}

bool microMatches(const Mesh& m) {
    return m.micro && m.micro->baseTriangles == m.triangleCount() && m.micro->baseVertices == m.vertexCount();
}

MicroMesh& mutableMicro(Mesh& m) {
    if (m.micro.use_count() > 1) m.micro = std::make_shared<MicroMesh>(*m.micro);
    return *m.micro;
}

size_t microMaxTriangles() {
    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
    // Per micro triangle about 0.6 grid points (level 4) x (2 bytes + 1 of mask + 6 on the GPU) + undo: ~6 bytes.
    return std::clamp<size_t>(memory / 10 * 5 / 6, 100'000'000, size_t(8'000'000'000));
}

int microLevelFor(const Mesh& m, size_t target) {
    const double nt = double(std::max<size_t>(m.triangleCount(), 1));
    int best = 1;
    double bestErr = 1e300;
    for (int l = 1; l <= MicroMesh::kMaxLevel; ++l) {
        const double err = std::abs(std::log(nt * std::pow(4.0, l) / double(std::max<size_t>(target, 1))));
        if (err < bestErr) bestErr = err, best = l;
    }
    return best;
}

glm::vec3 microPoint(const Mesh& m, uint32_t tri, uint32_t i, uint32_t j) {
    const MicroMesh& mm = *m.micro;
    MicroTriangle T;
    T.set(m, tri, mm.n);
    glm::vec3 s, nn;
    T.eval(i, j, s, nn);
    return s + nn * (float(mm.disp[size_t(tri) * mm.samples + MicroMesh::index(i, j, mm.n)]) * mm.step);
}

namespace {

// The micro triangle holding barycentric point w of a base triangle: its three grid points (i, j) and weights.
struct Cell {
    uint32_t i[3], j[3];
    float w[3];
};
Cell cellAt(const float wc[3], uint32_t n) {
    const float fi = std::clamp(wc[1], 0.0f, 1.0f) * float(n), fj = std::clamp(wc[2], 0.0f, 1.0f) * float(n);
    uint32_t i0 = std::min(uint32_t(fi), n - 1), j0 = std::min(uint32_t(fj), n - 1);
    if (i0 + j0 > n - 1) { // outside the last full cell along the hypotenuse
        if (fi >= fj) i0 = n - 1 - j0;
        else j0 = n - 1 - i0;
    }
    const float a = fi - float(i0), b = fj - float(j0);
    Cell c;
    if (a + b <= 1.0f || i0 + j0 + 2 > n) {
        c.i[0] = i0, c.j[0] = j0, c.i[1] = i0 + 1, c.j[1] = j0, c.i[2] = i0, c.j[2] = j0 + 1;
        c.w[0] = 1.0f - a - b, c.w[1] = a, c.w[2] = b;
    } else {
        c.i[0] = i0 + 1, c.j[0] = j0, c.i[1] = i0 + 1, c.j[1] = j0 + 1, c.i[2] = i0, c.j[2] = j0 + 1;
        c.w[0] = 1.0f - b, c.w[1] = a + b - 1.0f, c.w[2] = 1.0f - a;
    }
    return c;
}

} // namespace

glm::vec3 microPointAt(const Mesh& m, uint32_t tri, const float wc[3], glm::vec3* normal) {
    const MicroMesh& mm = *m.micro;
    MicroTriangle T;
    T.set(m, tri, mm.n);
    const Cell c = cellAt(wc, mm.n);
    glm::vec3 q[3];
    for (int k = 0; k < 3; ++k) {
        glm::vec3 s, nn;
        T.eval(c.i[k], c.j[k], s, nn);
        q[k] = s + nn * (float(mm.disp[size_t(tri) * mm.samples + MicroMesh::index(c.i[k], c.j[k], mm.n)]) * mm.step);
    }
    if (normal) {
        const glm::vec3 g = glm::cross(q[1] - q[0], q[2] - q[0]);
        const float len = glm::length(g);
        *normal = len > 0.0f ? g / len : glm::vec3(0.0f, 0.0f, 1.0f);
    }
    return q[0] * c.w[0] + q[1] * c.w[1] + q[2] * c.w[2];
}

// ---------------------------------------------------------------------------
// Divide / Delete
// ---------------------------------------------------------------------------

namespace {

// The most a base triangle's Phong surface leaves its plane (an upper bound).
float triangleBulge(const MicroTriangle& T) {
    float e = 0.0f;
    for (int k = 0; k < 3; ++k)
        for (int q = 0; q < 3; ++q) e = std::max(e, std::abs(glm::dot(T.p[q] - T.p[k], T.nrm[k])));
    return e * MicroMesh::kPhong;
}

} // namespace

void microRaiseBulge(Mesh& m) {
    if (!m.micro) return;
    MicroMesh& mm = *m.micro;
    const uint32_t nt = mm.baseTriangles, n = mm.n;
    const size_t block = 1 << 14;
    std::vector<float> bulge((nt + block - 1) / block, 0.0f);
    poolFor(nt, [&](size_t b, size_t e) {
        MicroTriangle T;
        float g = 0.0f;
        for (size_t t = b; t < e; ++t) {
            T.set(m, uint32_t(t), n);
            g = std::max(g, triangleBulge(T));
        }
        bulge[b / block] = g;
    }, block);
    for (float g : bulge) mm.bulgeMax = std::max(mm.bulgeMax, g);
}

bool microWantsOutOfCore(size_t points) {
    if (const char* e = std::getenv("SF_MICRO_OUT_OF_CORE"); e && *e) return std::string(e) == "1";
    if (const size_t limit = currentTierConfig().outOfCorePoints) return points > limit;
    size_t memory = 0;
#if 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 memory && points * 2 > memory / 4;
}

bool microDivide(Mesh& m, int level, std::string& error, int outOfCore) {
    if (level < 1 || level > MicroMesh::kMaxLevel) {
        error = "Micro level must be 1 to " + std::to_string(MicroMesh::kMaxLevel);
        return false;
    }
    const size_t nt = m.triangleCount();
    if (nt == 0) {
        error = "Nothing to divide";
        return false;
    }
    if (m.micro) {
        error = "This Part already has a micro level (Delete micro or Bake it first)";
        return false;
    }
    if (subdivLevelCount(m) > 0 && subdivCurrentLevel(m) != subdivLevelCount(m) - 1) {
        error = "Go to the highest subdivision level first: the micro level goes on top of it";
        return false;
    }
    if (!m.forgespheres.empty()) {
        error = "Forge Sphere Parts can't have a micro level (make an adaptive skin first)";
        return false;
    }
    if (!m.tube.empty()) {
        error = "Tube Parts can't have a micro level (Bake the tube first)";
        return false;
    }
    if (!m.layers.empty()) {
        error = "Sculpt layers can't carry a micro level yet: bake or delete the layers first";
        return false;
    }
    if (nt > (size_t(1) << 30)) {
        error = "Too many base triangles for a micro level";
        return false;
    }
    const size_t micro = nt << (2 * level);
    if (micro > microMaxTriangles()) {
        char buf[200];
        std::snprintf(buf, sizeof buf, "%.0fM micro triangles is more than this computer allows (%.0fM): pick a lower micro level",
                      double(micro) / 1e6, double(microMaxTriangles()) / 1e6);
        error = buf;
        return false;
    }
    if (m.normals.size() != m.vertexCount()) m.recomputeAllNormals();
    auto mm = std::make_shared<MicroMesh>();
    mm->level = level;
    mm->n = 1u << level;
    mm->samples = (mm->n + 1) * (mm->n + 2) / 2;
    mm->baseTriangles = uint32_t(nt);
    mm->baseVertices = uint32_t(m.vertexCount());
    if (outOfCore < 0 ? microWantsOutOfCore(nt * mm->samples) : outOfCore == 1) {
        std::string why;
        mm->disp.assignMapped(nt * mm->samples, why); // (falls back to memory)
    } else {
        mm->disp.assign(nt * mm->samples, 0);
    }
    mm->triRange.assign(nt, 0);
    mm->dirtyBits.assign((nt + 63) / 64, 0);
    mm->ensureTopology(m);
    // Edge length and bulge, in parallel blocks (combined in order: deterministic).
    const size_t block = 1 << 14, blocks = (nt + block - 1) / block;
    std::vector<double> edgeSum(blocks, 0.0);
    std::vector<float> bulge(blocks, 0.0f);
    poolFor(nt, [&](size_t b, size_t e) {
        double s = 0.0;
        float g = 0.0f;
        MicroTriangle T;
        for (size_t t = b; t < e; ++t) {
            T.set(m, uint32_t(t), mm->n);
            s += double(glm::distance(T.p[0], T.p[1]) + glm::distance(T.p[1], T.p[2]) + glm::distance(T.p[2], T.p[0]));
            g = std::max(g, triangleBulge(T));
        }
        edgeSum[b / block] = s;
        bulge[b / block] = g;
    }, block);
    double total = 0.0;
    for (size_t i = 0; i < blocks; ++i) {
        total += edgeSum[i];
        mm->bulgeMax = std::max(mm->bulgeMax, bulge[i]);
    }
    const float avgEdge = float(total / double(nt * 3));
    mm->baseEdge = avgEdge;
    // 1/4096 of a base edge per unit: +/-8 base edges of range, steps far below a micro edge (1/256 of one at
    // level 4). Brushes widen the range when they need more (MicroStroke).
    mm->step = std::max(avgEdge / 4096.0f, 1e-12f);
    mm->serial = MicroMesh::newSerial();
    mm->markAllDirty();
    m.micro = std::move(mm);
    m.topologyDirty = true; // the renderer draws it differently
    return true;
}

bool microAttach(Mesh& m, int level, float step, MicroStore disp, std::vector<uint8_t> mask, std::string& error) {
    if (level < 1 || level > MicroMesh::kMaxLevel || !(step > 0.0f) || !std::isfinite(step)) {
        error = "Project micro level is invalid";
        return false;
    }
    const size_t nt = m.triangleCount();
    const uint32_t n = 1u << level, S = (n + 1) * (n + 2) / 2;
    if (disp.size() != nt * S || (!mask.empty() && mask.size() != disp.size())) {
        error = "Project micro level doesn't fit its mesh";
        return false;
    }
    if (m.normals.size() != m.vertexCount()) m.recomputeAllNormals();
    auto mm = std::make_shared<MicroMesh>();
    mm->level = level;
    mm->n = n;
    mm->samples = S;
    mm->step = step;
    mm->baseTriangles = uint32_t(nt);
    mm->baseVertices = uint32_t(m.vertexCount());
    mm->disp = std::move(disp);
    mm->mask = std::move(mask);
    mm->triRange.assign(nt, 0);
    mm->dirtyBits.assign((nt + 63) / 64, 0);
    const size_t block = 1 << 12, blocks = (nt + block - 1) / block;
    std::vector<float> bulge(blocks, 0.0f);
    poolFor(nt, [&](size_t b, size_t e) {
        MicroTriangle T;
        float g = 0.0f;
        for (size_t t = b; t < e; ++t) {
            const int16_t* d = mm->disp.data() + t * S;
            int r = 0;
            for (uint32_t k = 0; k < S; ++k) r = std::max(r, std::abs(int(d[k])));
            mm->triRange[t] = uint16_t(std::min(r, 32767));
            T.set(m, uint32_t(t), n);
            g = std::max(g, triangleBulge(T));
        }
        bulge[b / block] = g;
    }, block);
    for (float g : bulge) mm->bulgeMax = std::max(mm->bulgeMax, g);
    {
        double e = 0.0;
        for (size_t t = 0; t < nt; ++t) {
            const glm::uvec3 tr = m.triangles[t];
            e += double(glm::distance(m.positions[tr.x], m.positions[tr.y]) + glm::distance(m.positions[tr.y], m.positions[tr.z]) +
                        glm::distance(m.positions[tr.z], m.positions[tr.x]));
        }
        mm->baseEdge = float(e / double(std::max<size_t>(nt * 3, 1)));
    }
    for (uint16_t r : mm->triRange) mm->rangeMax = std::max(mm->rangeMax, r);
    mm->ensureTopology(m);
    mm->serial = MicroMesh::newSerial();
    mm->markAllDirty();
    m.micro = std::move(mm);
    m.topologyDirty = true;
    return true;
}

void microDelete(Mesh& m) {
    if (!m.micro) return;
    m.micro.reset();
    m.topologyDirty = true;
}

// ---------------------------------------------------------------------------
// Picking
// ---------------------------------------------------------------------------

namespace {

bool rayTriangle(const glm::vec3& o, const glm::vec3& d, const glm::vec3& a, const glm::vec3& b, const glm::vec3& c, float& t) {
    const glm::vec3 e1 = b - a, e2 = c - a, pv = glm::cross(d, e2);
    const float det = glm::dot(e1, pv);
    if (std::abs(det) < 1e-30f) return false;
    const float inv = 1.0f / det;
    const glm::vec3 tv = o - a;
    const float u = glm::dot(tv, pv) * inv;
    if (u < 0.0f || u > 1.0f) return false;
    const glm::vec3 qv = glm::cross(tv, e1);
    const float v = glm::dot(d, qv) * inv;
    if (v < 0.0f || u + v > 1.0f) return false;
    t = glm::dot(e2, qv) * inv;
    return t > 0.0f;
}

} // namespace

namespace {

// Brings m's Reach up to date with `bvh` (call with reach.lock held): a full pass when the BVH, the step or
// everything changed, else the triangles marked since raise their leaves and ancestors.
void syncReach(const Mesh& m, const BVH& bvh) {
    const MicroMesh& mm = *m.micro;
    MicroMesh::Reach& r = mm.reach;
    const size_t words = (size_t(mm.baseTriangles) + 63) / 64;
    const bool full = r.all || r.bvh != &bvh || r.structure != bvh.structureSerial() || r.step != mm.step ||
                      r.pad.size() != bvh.nodeCount() || r.bits.size() != words;
    if (full) {
        r.bvh = &bvh, r.structure = bvh.structureSerial(), r.step = mm.step, r.all = false;
        r.bits.assign(words, 0);
        const size_t nodes = bvh.nodeCount();
        r.pad.assign(nodes, 0.0f);
        poolFor(nodes, [&](size_t b, size_t e) {
            for (size_t i = b; i < e; ++i) {
                uint16_t most = 0;
                for (uint32_t t : bvh.leafTriangles(uint32_t(i)))
                    if (t < mm.triRange.size()) most = std::max(most, mm.triRange[t]);
                r.pad[i] = float(most) * mm.step;
            }
        }, 1 << 12);
        for (size_t i = nodes; i-- > 0;)
            if (bvh.isInner(uint32_t(i))) {
                const uint32_t c = bvh.leftChild(uint32_t(i));
                r.pad[i] = std::max(r.pad[c], r.pad[c + 1]);
            }
        return;
    }
    for (size_t w = 0; w < words; ++w) {
        if (!r.bits[w]) continue;
        const uint64_t bits = std::atomic_ref<uint64_t>(r.bits[w]).exchange(0);
        for (uint64_t b = bits; b; b &= b - 1) {
            const uint32_t t = uint32_t(w * 64 + size_t(std::countr_zero(b)));
            const float v = float(mm.triRange[t]) * mm.step;
            for (uint32_t node = bvh.leafOf(t); node != ~0u && r.pad[node] < v; node = bvh.parentOf(node)) {
                r.pad[node] = v;
                if (node == 0) break;
            }
        }
    }
}

} // namespace

void microQueryTriangles(const Mesh& m, const BVH& bvh, const glm::vec3& center, float radius, std::vector<uint32_t>& out) {
    const MicroMesh& mm = *m.micro;
    std::lock_guard<std::mutex> hold(mm.reach.lock);
    syncReach(m, bvh);
    bvh.queryTrianglesPadded(m, center, radius, mm.reach.pad, mm.bulgeMax, out);
}

void microRayTriangles(const Mesh& m, const BVH& bvh, const glm::vec3& origin, const glm::vec3& dir, std::vector<uint32_t>& out) {
    const MicroMesh& mm = *m.micro;
    std::lock_guard<std::mutex> hold(mm.reach.lock);
    syncReach(m, bvh);
    bvh.rayTrianglesPadded(m, origin, dir, mm.reach.pad, mm.bulgeMax, out);
}

bool microRaycast(const Mesh& m, const BVH& bvh, const glm::vec3& origin, const glm::vec3& dir, RayHit& hit) {
    if (!microMatches(m)) return bvh.raycast(m, origin, dir, hit);
    const MicroMesh& mm = *m.micro;
    RayHit base;
    if (!bvh.raycast(m, origin, dir, base)) return false;
    std::vector<uint32_t> cand;
    const auto traceStart = std::chrono::steady_clock::now();
    microRayTriangles(m, bvh, origin, dir, cand);
    static const bool trace = [] { const char* e = std::getenv("SF_MICRO_TRACE"); return e && e[0] == '1'; }();
    if (trace)
        std::fprintf(stderr, "micropick %zu candidates in %.1f ms (pad root %.4f, bulgeMax %.4f)\n", cand.size(),
                     std::chrono::duration<double, std::milli>(std::chrono::steady_clock::now() - traceStart).count(),
                     mm.reach.pad.empty() ? 0.0 : double(mm.reach.pad[0]), double(mm.bulgeMax));
    // Only the triangles whose own reach (their bulge and displacement range) the ray passes through.
    const glm::vec3 inv(1.0f / (std::abs(dir.x) > 1e-20f ? dir.x : 1e-20f), 1.0f / (std::abs(dir.y) > 1e-20f ? dir.y : 1e-20f),
                        1.0f / (std::abs(dir.z) > 1e-20f ? dir.z : 1e-20f));
    std::erase_if(cand, [&](uint32_t t) {
        if (t == base.triangle) return false;
        MicroTriangle T;
        T.set(m, t, mm.n);
        const float grow = triangleBulge(T) + float(mm.triRange[t]) * mm.step;
        const glm::vec3 lo = glm::min(T.p[0], glm::min(T.p[1], T.p[2])) - grow, hi = glm::max(T.p[0], glm::max(T.p[1], T.p[2])) + grow;
        const glm::vec3 t0 = (lo - origin) * inv, t1 = (hi - origin) * inv;
        const glm::vec3 tn = glm::min(t0, t1), tf = glm::max(t0, t1);
        const float enter = std::max({tn.x, tn.y, tn.z, 0.0f}), leave = std::min({tf.x, tf.y, tf.z});
        return enter > leave;
    });
    if (std::find(cand.begin(), cand.end(), base.triangle) == cand.end()) cand.push_back(base.triangle);
    constexpr size_t kMaxCandidates = 4096;
    if (cand.size() > kMaxCandidates) { // a huge displacement range: rank by distance and keep the nearest
        std::nth_element(cand.begin(), cand.begin() + kMaxCandidates, cand.end(), [&](uint32_t a, uint32_t b) {
            auto c = [&](uint32_t t) {
                const glm::uvec3 tr = m.triangles[t];
                return glm::distance(base.position, (m.positions[tr.x] + m.positions[tr.y] + m.positions[tr.z]) / 3.0f);
            };
            return c(a) < c(b);
        });
        cand.resize(kMaxCandidates);
    }
    const uint32_t n = mm.n, S = mm.samples;
    struct Best {
        float t = std::numeric_limits<float>::max();
        uint32_t tri = 0;
        glm::vec3 a{0.0f}, b{0.0f}, c{0.0f};
    };
    const size_t block = 4;
    std::vector<Best> best((cand.size() + block - 1) / block);
    poolFor(cand.size(), [&](size_t b0, size_t e0) {
        thread_local std::vector<glm::vec3> P;
        P.resize(S);
        Best bb;
        MicroTriangle T;
        for (size_t ci = b0; ci < e0; ++ci) {
            const uint32_t tri = cand[ci];
            if (m.triangleHidden(tri)) continue;
            T.set(m, tri, n);
            const int16_t* g = mm.disp.data() + size_t(tri) * S;
            uint32_t idx = 0;
            for (uint32_t j = 0; j <= n; ++j)
                for (uint32_t i = 0; i + j <= n; ++i, ++idx) {
                    glm::vec3 s, nn;
                    T.eval(i, j, s, nn);
                    P[idx] = s + nn * (float(g[idx]) * mm.step);
                }
            for (uint32_t j = 0; j < n; ++j) {
                const uint32_t row = MicroMesh::index(0, j, n), next = MicroMesh::index(0, j + 1, n);
                for (uint32_t i = 0; i + j < n; ++i) {
                    float t;
                    const glm::vec3 &a = P[row + i], &b = P[row + i + 1], &c = P[next + i];
                    if (rayTriangle(origin, dir, a, b, c, t) && t < bb.t) bb = {t, tri, a, b, c};
                    if (i + j + 1 < n) {
                        const glm::vec3 &d = P[next + i + 1];
                        if (rayTriangle(origin, dir, b, d, c, t) && t < bb.t) bb = {t, tri, b, d, c};
                    }
                }
            }
        }
        best[b0 / block] = bb;
    }, block, 2);
    Best win;
    for (const Best& b : best)
        if (b.t < win.t) win = b;
    if (win.t == std::numeric_limits<float>::max()) {
        // Missed every micro triangle near the base hit (a grazing ray): the micro point under the base hit.
        const glm::uvec3 tr = m.triangles[base.triangle];
        const glm::vec3 a = m.positions[tr.x], b = m.positions[tr.y], c = m.positions[tr.z];
        const glm::vec3 v0 = b - a, v1 = c - a, v2 = base.position - a;
        const float d00 = glm::dot(v0, v0), d01 = glm::dot(v0, v1), d11 = glm::dot(v1, v1), d20 = glm::dot(v2, v0),
                    d21 = glm::dot(v2, v1), den = d00 * d11 - d01 * d01;
        float w[3] = {1.0f, 0.0f, 0.0f};
        if (std::abs(den) > 0.0f) {
            w[1] = (d11 * d20 - d01 * d21) / den;
            w[2] = (d00 * d21 - d01 * d20) / den;
            w[0] = 1.0f - w[1] - w[2];
        }
        hit = base;
        hit.position = microPointAt(m, base.triangle, w, &hit.normal);
        hit.t = glm::dot(hit.position - origin, dir);
        return true;
    }
    hit.t = win.t;
    hit.triangle = win.tri;
    hit.position = origin + dir * win.t;
    const glm::vec3 g = glm::cross(win.b - win.a, win.c - win.a);
    const float len = glm::length(g);
    hit.normal = len > 0.0f ? g / len : base.normal;
    return true;
}

bool surfaceRaycast(const Mesh& m, const BVH& bvh, const glm::vec3& origin, const glm::vec3& dir, RayHit& hit) {
    if (m.micro && microMatches(m)) return microRaycast(m, bvh, origin, dir, hit);
    return bvh.raycast(m, origin, dir, hit);
}

// ---------------------------------------------------------------------------
// Shading for the renderer
// ---------------------------------------------------------------------------

namespace {

constexpr int kPartialFloats = 5; // normal sum (3), neighbour displacement sum, neighbour count

uint32_t encodeShade(glm::vec3 nrm, float curvature, uint8_t mask) {
    const float l1 = std::abs(nrm.x) + std::abs(nrm.y) + std::abs(nrm.z);
    glm::vec2 e(0.0f);
    if (l1 > 0.0f) {
        nrm /= l1;
        e = glm::vec2(nrm.x, nrm.y);
        if (nrm.z < 0.0f)
            e = glm::vec2((1.0f - std::abs(nrm.y)) * (nrm.x >= 0.0f ? 1.0f : -1.0f),
                          (1.0f - std::abs(nrm.x)) * (nrm.y >= 0.0f ? 1.0f : -1.0f));
    }
    // (rounding by +0.5 and truncation: the values are >= 0 there, and lround costs more than the rest of a point)
    auto q = [](float v) { return uint32_t(std::clamp((v * 0.5f + 0.5f) * 255.0f + 0.5f, 0.0f, 255.0f)); };
    const float c = std::clamp(curvature, -1.0f, 1.0f);
    const float s = (c >= 0.0f ? 1.0f : -1.0f) * std::sqrt(std::abs(c));
    const uint32_t cq = uint32_t(std::clamp(s * 127.0f + 128.5f, 1.0f, 255.0f));
    return q(e.x) | q(e.y) << 8 | cq << 16 | uint32_t(mask) << 24;
}

// The grid of one base triangle: positions, then per point the sum of the face normals of its micro triangles
// (area weighted) and of its neighbours' displacements, within this triangle.
struct GridWork {
    std::vector<glm::vec3> pos, nsum;
    std::vector<float> dsum, cnt;
    void compute(const Mesh& m, const MicroMesh& mm, uint32_t tri) {
        const uint32_t n = mm.n, S = mm.samples;
        pos.resize(S);
        nsum.assign(S, glm::vec3(0.0f));
        dsum.assign(S, 0.0f);
        cnt.assign(S, 0.0f);
        MicroTriangle T;
        T.set(m, tri, n);
        const int16_t* g = mm.disp.data() + size_t(tri) * S;
        uint32_t idx = 0;
        for (uint32_t j = 0; j <= n; ++j)
            for (uint32_t i = 0; i + j <= n; ++i, ++idx) {
                glm::vec3 s, nn;
                T.eval(i, j, s, nn);
                pos[idx] = s + nn * (float(g[idx]) * mm.step);
            }
        for (uint32_t j = 0; j < n; ++j) {
            const uint32_t row = MicroMesh::index(0, j, n), next = MicroMesh::index(0, j + 1, n);
            for (uint32_t i = 0; i + j < n; ++i) {
                const uint32_t a = row + i, b = row + i + 1, c = next + i;
                face(a, b, c, g, true);
                if (i + j + 1 < n) face(b, next + i + 1, c, g, false);
            }
        }
    }
    // The sums at some edge points only (a triangle of the outer ring: the points it shares with the ones written):
    // edges e (bit e: its points between the corners) and corners c (bit 3 + c). The micro triangles touching
    // them alone, added in the same order as compute(), so those sums come out bit-identical to a whole grid's
    // at a fraction of its cost.
    void computePart(const Mesh& m, const MicroMesh& mm, uint32_t tri, unsigned parts) {
        const uint32_t n = mm.n, S = mm.samples;
        pos.resize(S);
        nsum.resize(S);
        dsum.resize(S);
        cnt.resize(S);
        need.assign(S, 0);
        for (int e = 0; e < 3; ++e) {
            uint32_t i, j;
            if (parts & (8u << e)) MicroMesh::edgePoint(e, 0, n, i, j), need[MicroMesh::index(i, j, n)] = 1;
            if (parts & (1u << e))
                for (uint32_t k = 1; k < n; ++k) MicroMesh::edgePoint(e, k, n, i, j), need[MicroMesh::index(i, j, n)] = 1;
        }
        MicroTriangle T;
        T.set(m, tri, n);
        const int16_t* g = mm.disp.data() + size_t(tri) * S;
        auto at = [&](uint32_t i, uint32_t j) { // (each point once, the first time a triangle needs it)
            const uint32_t idx = MicroMesh::index(i, j, n);
            if (need[idx] & 2) return idx;
            need[idx] |= 2;
            glm::vec3 s, nn;
            T.eval(i, j, s, nn);
            pos[idx] = s + nn * (float(g[idx]) * mm.step);
            nsum[idx] = glm::vec3(0.0f), dsum[idx] = 0.0f, cnt[idx] = 0.0f; // (the others aren't read)
            return idx;
        };
        // (the micro triangles that can touch an edge: row 0, and the first and the last two of every other row)
        for (uint32_t j = 0; j < n; ++j) {
            const uint32_t row = MicroMesh::index(0, j, n), next = MicroMesh::index(0, j + 1, n), last = n - j;
            for (uint32_t i = 0; i < last; i = j == 0 || i + 3 >= last ? i + 1 : last - 2) {
                const uint32_t a = row + i, b = row + i + 1, c = next + i;
                if ((need[a] | need[b] | need[c]) & 1) face(at(i, j), at(i + 1, j), at(i, j + 1), g, true);
                if (i + j + 1 < n && ((need[b] | need[next + i + 1] | need[c]) & 1)) face(at(i + 1, j), at(i + 1, j + 1), at(i, j + 1), g, false);
            }
        }
    }

private:
    std::vector<uint8_t> need; // computePart: 1 = a wanted sum, 2 = its position computed
    // Micro triangle a b c (counter-clockwise) into the sums of its corners; `up` also adds its lattice edges a-b,
    // a-c, b-c (each once: every edge belongs to one upward triangle).
    void face(uint32_t a, uint32_t b, uint32_t c, const int16_t* g, bool up) {
        const glm::vec3 f = glm::cross(pos[b] - pos[a], pos[c] - pos[a]);
        nsum[a] += f, nsum[b] += f, nsum[c] += f;
        if (!up) return;
        const float da = g[a], db = g[b], dc = g[c];
        dsum[a] += db + dc, dsum[b] += da + dc, dsum[c] += da + db;
        cnt[a] += 2.0f, cnt[b] += 2.0f, cnt[c] += 2.0f;
    }
};

} // namespace

void MicroShader::shade(const Mesh& m, std::span<const uint32_t> dirty, bool all, std::vector<uint32_t>& written,
                        const std::function<uint32_t*(uint32_t tri)>& out, const Prepare& prepare, bool grow,
                        std::vector<uint32_t>* outer) {
    written.clear();
    if (outer) outer->clear();
    if (!m.micro) return;
    if (!all) {
        shadeSet(m, dirty, grow, written, out, prepare, grow ? nullptr : outer);
        return;
    }
    // Everything: in runs of triangles (neighbours by index on levels made by Divide), each with the ring its
    // shared points need, so the edge sums stay a few MB instead of 20 bytes per edge point of the whole mesh.
    const uint32_t nt = m.micro->baseTriangles;
    constexpr uint32_t kRun = 1u << 16;
    std::vector<uint32_t> run;
    for (uint32_t b = 0; b < nt; b += kRun) {
        run.resize(std::min(kRun, nt - b));
        for (uint32_t i = 0; i < run.size(); ++i) run[i] = b + i;
        shadeSet(m, run, false, written, out, prepare);
    }
}

void MicroShader::shadeSet(const Mesh& m, std::span<const uint32_t> dirty, bool grow, std::vector<uint32_t>& written,
                           const std::function<uint32_t*(uint32_t tri)>& out, const Prepare& prepare, std::vector<uint32_t>* outer) {
    const MicroMesh& mm = *m.micro;
    const uint32_t n = mm.n, S = mm.samples, nt = mm.baseTriangles;
    if (mm.edgeNeighbor.size() != size_t(nt) * 3) return; // (ensureTopology first)
    if (stamp_.size() != nt) {
        stamp_.assign(nt, 0);
        slot_.assign(nt, 0);
        epoch_ = 0;
    }
    if (vstamp_.size() != m.vertexCount()) vstamp_.assign(m.vertexCount(), 0);
    if (epoch_ > 0xFFFFFF00u) {
        std::fill(stamp_.begin(), stamp_.end(), 0);
        std::fill(vstamp_.begin(), vstamp_.end(), 0);
        epoch_ = 0;
    }
    // R = the triangles to write: dirty ones and those sharing a vertex; R2 = R and those sharing a vertex with
    // R (whose edge sums the shared points need). stamp_: epoch + 1 = in R, epoch + 2 = only in R2.
    const uint32_t inR = ++epoch_;
    const uint32_t inR2 = ++epoch_;
    auto vertexRing = [&](const std::vector<uint32_t>& from, std::vector<uint32_t>& into, uint32_t mark, uint32_t vmark) {
        for (uint32_t t : from) {
            const glm::uvec3 tri = m.triangles[t];
            for (int k = 0; k < 3; ++k) {
                if (vstamp_[tri[k]] == vmark) continue;
                vstamp_[tri[k]] = vmark;
                for (uint32_t u : m.vertexTriangles(tri[k]))
                    if (stamp_[u] != inR && stamp_[u] != mark) {
                        stamp_[u] = mark;
                        into.push_back(u);
                    }
            }
        }
    };
    ring_.clear();
    ring2_.clear();
    for (uint32_t t : dirty)
        if (t < nt && stamp_[t] != inR) stamp_[t] = inR, ring_.push_back(t);
    if (grow) {
        seed_.assign(ring_.begin(), ring_.end());
        grown_.clear();
        const uint32_t v1 = ++epoch_;
        vertexRing(seed_, grown_, inR, v1); // (marks them inR directly: they're written too)
        ring_.insert(ring_.end(), grown_.begin(), grown_.end());
    }
    const uint32_t v2 = ++epoch_;
    vertexRing(ring_, ring2_, inR2, v2);
    if (outer) outer->insert(outer->end(), ring2_.begin(), ring2_.end());
    for (size_t i = 0; i < ring_.size(); ++i) slot_[ring_[i]] = uint32_t(i);
    for (size_t i = 0; i < ring2_.size(); ++i) slot_[ring2_[i]] = uint32_t(ring_.size() + i);
    if (prepare) prepare(ring_);
    const size_t slots = ring_.size() + ring2_.size();
    const size_t edgePoints = size_t(3) * n;
    partial_.resize(slots * edgePoints * kPartialFloats);
    auto tileOf = [&](size_t i) { return i < ring_.size() ? ring_[i] : ring2_[i - ring_.size()]; };
    auto microEdge = [&](uint32_t tri) {
        const glm::uvec3 t = m.triangles[tri];
        const float e = glm::distance(m.positions[t.x], m.positions[t.y]) + glm::distance(m.positions[t.y], m.positions[t.z]) +
                        glm::distance(m.positions[t.z], m.positions[t.x]);
        return std::max(e / (3.0f * float(n)), 1e-20f);
    };
    auto finish = [&](const glm::vec3& ns, float ds, float c, float d, float h, uint8_t mk) {
        const float curv = c > 0.0f ? (ds / c - d) * mm.step / h : 0.0f;
        return encodeShade(ns, curv, mk); // (unnormalized: the encoding divides by its L1 length; zero = +z either way)
    };
    // Phase 1: every R2 triangle's edge partials; R triangles' interior points written.
    poolFor(slots, [&](size_t b, size_t e) {
        thread_local GridWork w;
        for (size_t s = b; s < e; ++s) {
            const uint32_t tri = tileOf(s);
            if (s < ring_.size()) {
                w.compute(m, mm, tri);
            } else { // the outer ring: the sums at the points it shares with R (whose vertices are marked v2)
                const glm::uvec3 tv = m.triangles[tri];
                unsigned parts = 0;
                for (int k = 0; k < 3; ++k) {
                    const bool here = vstamp_[tv[k]] == v2, next = vstamp_[tv[(k + 1) % 3]] == v2;
                    parts |= (here ? 8u << k : 0u) | (here && next ? 1u << k : 0u);
                }
                w.computePart(m, mm, tri, parts);
            }
            float* part = partial_.data() + s * edgePoints * kPartialFloats;
            for (int ed = 0; ed < 3; ++ed)
                for (uint32_t k = 0; k < n; ++k) {
                    uint32_t i, j;
                    MicroMesh::edgePoint(ed, k, n, i, j);
                    const uint32_t idx = MicroMesh::index(i, j, n);
                    float* p = part + (size_t(ed) * n + k) * kPartialFloats;
                    p[0] = w.nsum[idx].x, p[1] = w.nsum[idx].y, p[2] = w.nsum[idx].z, p[3] = w.dsum[idx], p[4] = w.cnt[idx];
                }
            if (s >= ring_.size()) continue;
            uint32_t* dst = out(tri);
            const int16_t* g = mm.disp.data() + size_t(tri) * S;
            const uint8_t* mk = mm.hasMask() ? mm.mask.data() + size_t(tri) * S : nullptr;
            const float h = microEdge(tri);
            for (uint32_t j = 1; j + 1 < n; ++j)
                for (uint32_t i = 1; i + j < n; ++i) {
                    const uint32_t idx = MicroMesh::index(i, j, n);
                    dst[idx] = finish(w.nsum[idx], w.dsum[idx], w.cnt[idx], float(g[idx]), h, mk ? mk[idx] : 0);
                }
        }
    }, 16);
    // Phase 2: R triangles' edge and corner points, summed with the other triangles holding them.
    poolFor(ring_.size(), [&](size_t b, size_t e) {
        for (size_t s = b; s < e; ++s) {
            const uint32_t tri = ring_[s];
            uint32_t* dst = out(tri);
            const int16_t* g = mm.disp.data() + size_t(tri) * S;
            const uint8_t* mk = mm.hasMask() ? mm.mask.data() + size_t(tri) * S : nullptr;
            const float h = microEdge(tri);
            const float* own = partial_.data() + s * edgePoints * kPartialFloats;
            const glm::uvec3 ttri = m.triangles[tri];
            for (int ed = 0; ed < 3; ++ed) {
                const uint32_t nb = mm.edgeNeighbor[size_t(tri) * 3 + size_t(ed)];
                const float* other = nullptr;
                bool reversed = true;
                int f = 0;
                if (nb != MicroMesh::kNone && (stamp_[nb >> 2] == inR || stamp_[nb >> 2] == inR2)) {
                    const uint32_t u = nb >> 2;
                    f = int(nb & 3);
                    other = partial_.data() + size_t(slot_[u]) * edgePoints * kPartialFloats;
                    reversed = m.triangles[u][f] != ttri[ed]; // usual: the neighbour runs the edge the other way
                }
                for (uint32_t k = 1; k < n; ++k) {
                    const float* p = own + (size_t(ed) * n + k) * kPartialFloats;
                    glm::vec3 ns(p[0], p[1], p[2]);
                    float ds = p[3], c = p[4];
                    if (other) {
                        const float* q = other + (size_t(f) * n + (reversed ? n - k : k)) * kPartialFloats;
                        ns += glm::vec3(q[0], q[1], q[2]);
                        ds += q[3];
                        c += q[4];
                    }
                    uint32_t i, j;
                    MicroMesh::edgePoint(ed, k, n, i, j);
                    const uint32_t idx = MicroMesh::index(i, j, n);
                    dst[idx] = finish(ns, ds, c, float(g[idx]), h, mk ? mk[idx] : 0);
                }
                // The corner at the start of this edge: every triangle around the vertex.
                const uint32_t v = ttri[ed];
                glm::vec3 ns(0.0f);
                float ds = 0.0f, c = 0.0f;
                for (uint32_t u : m.vertexTriangles(v)) {
                    if (stamp_[u] != inR && stamp_[u] != inR2) continue;
                    const glm::uvec3 ut = m.triangles[u];
                    const int corner = ut.x == v ? 0 : ut.y == v ? 1 : 2;
                    const float* q = partial_.data() + (size_t(slot_[u]) * edgePoints + size_t(corner) * n) * kPartialFloats;
                    ns += glm::vec3(q[0], q[1], q[2]);
                    ds += q[3];
                    c += q[4];
                }
                uint32_t i, j;
                MicroMesh::edgePoint(ed, 0, n, i, j);
                const uint32_t idx = MicroMesh::index(i, j, n);
                dst[idx] = finish(ns, ds, c, float(g[idx]), h, mk ? mk[idx] : 0);
            }
        }
    }, 16);
    written.insert(written.end(), ring_.begin(), ring_.end());
}

// ---------------------------------------------------------------------------
// Undo
// ---------------------------------------------------------------------------

void MicroUndo::swapWith(Mesh& m) {
    if (swapWhole) {
        std::swap(m.micro, whole);
        if (m.micro) {
            m.micro->markAllDirty();
            m.micro->ensureTopology(m);
            if (m.micro->dirtyBits.size() != (size_t(m.micro->baseTriangles) + 63) / 64)
                m.micro->dirtyBits.assign((size_t(m.micro->baseTriangles) + 63) / 64, 0);
        }
        m.topologyDirty = true;
        return;
    }
    if (!m.micro || !microMatches(m) || m.micro->samples != samples) return;
    MicroMesh& mm = mutableMicro(m);
    if (mm.focus) mm.focus->ensureFull(mm, tris, true); // (undo writes full tiles only)
    const size_t S = samples;
    // Values kept in another step size (the range grew since): convert to the current one.
    if (!journal && step != mm.step && step > 0.0f) {
        const float r = step / mm.step;
        for (int16_t& v : disp) v = int16_t(std::clamp(std::lround(float(v) * r), -32767L, 32767L));
        step = mm.step;
    }
    if (maskAdded) {
        if (mm.hasMask()) {
            poolFor(tris.size(), [&](size_t b, size_t e) {
                for (size_t i = b; i < e; ++i)
                    std::swap_ranges(mask.begin() + std::ptrdiff_t(i * S), mask.begin() + std::ptrdiff_t((i + 1) * S),
                                     mm.mask.begin() + std::ptrdiff_t(size_t(tris[i]) * S));
            }, 64);
            std::vector<uint8_t>().swap(mm.mask);
        } else {
            mm.mask.assign(mm.disp.size(), 0);
            poolFor(tris.size(), [&](size_t b, size_t e) {
                for (size_t i = b; i < e; ++i)
                    std::swap_ranges(mask.begin() + std::ptrdiff_t(i * S), mask.begin() + std::ptrdiff_t((i + 1) * S),
                                     mm.mask.begin() + std::ptrdiff_t(size_t(tris[i]) * S));
            }, 64);
        }
        mm.maskDirty = true;
    } else if (!mask.empty() && mm.hasMask()) {
        poolFor(tris.size(), [&](size_t b, size_t e) {
            for (size_t i = b; i < e; ++i)
                std::swap_ranges(mask.begin() + std::ptrdiff_t(i * S), mask.begin() + std::ptrdiff_t((i + 1) * S),
                                 mm.mask.begin() + std::ptrdiff_t(size_t(tris[i]) * S));
        }, 64);
    }
    if (journal) { // the stroke's change: subtract it (undo) or add it back (redo)
        std::vector<int16_t> change(tris.size() * S, 0);
        if (!microUnpackTiles(packed.data(), packed.size(), tris.size(), samples, change.data())) return;
        poolFor(tris.size(), [&](size_t b, size_t e) { // (stored as differences to the point before, see MicroUndo)
            const uint32_t n = mm.n;
            for (size_t t = b; t < e; ++t) {
                int16_t* c = change.data() + t * S;
                uint32_t p = 0;
                for (uint32_t j = 0; j <= n; ++j)
                    for (uint32_t i = 0; i + j <= n; ++i, ++p) {
                        int v;
                        if (p == 0) v = firsts[t];
                        else if (i > 0) v = int(c[p - 1]) + int(c[p]);
                        else v = int(c[MicroMesh::index(0, j - 1, n)]) + int(c[p]);
                        c[p] = int16_t(std::clamp(v, -32767, 32767));
                    }
            }
        }, 256);
        const float ratio = step / mm.step; // (the range grew since: the change in today's units)
        const int sgn = applied ? -1 : 1;
        poolFor(tris.size(), [&](size_t b, size_t e) {
            for (size_t i = b; i < e; ++i) {
                int16_t* g = mm.disp.data() + size_t(tris[i]) * S;
                int r = 0;
                for (size_t k = 0; k < S; ++k) {
                    const float c = ratio == 1.0f ? float(change[i * S + k]) : float(change[i * S + k]) * ratio;
                    const int v = std::clamp(int(g[k]) + sgn * int(std::lround(c)), -32767, 32767);
                    g[k] = int16_t(v);
                    r = std::max(r, std::abs(v));
                }
                mm.triRange[tris[i]] = uint16_t(std::max<int>(r, mm.triRange[tris[i]]));
            }
        }, 64);
        applied = !applied;
        for (uint32_t t : tris) mm.rangeMax = std::max(mm.rangeMax, mm.triRange[t]);
    }
    if (!disp.empty()) {
        poolFor(tris.size(), [&](size_t b, size_t e) {
            for (size_t i = b; i < e; ++i) {
                int16_t* g = mm.disp.data() + size_t(tris[i]) * S;
                std::swap_ranges(disp.begin() + std::ptrdiff_t(i * S), disp.begin() + std::ptrdiff_t((i + 1) * S), g);
                int r = 0;
                for (size_t k = 0; k < S; ++k) r = std::max(r, std::abs(int(g[k])));
                mm.triRange[tris[i]] = uint16_t(r);
            }
        }, 64);
        for (uint32_t t : tris) mm.rangeMax = std::max(mm.rangeMax, mm.triRange[t]);
    }
    for (uint32_t t : tris) mm.markDirty(t);
    ++mm.revision;
}

size_t MicroUndo::bytes() const {
    return tris.size() * sizeof(uint32_t) + keys.size() * sizeof(uint64_t) + packed.size() + firsts.size() * sizeof(int16_t) + disp.size() * sizeof(int16_t) +
           mask.size() + (swapWhole && whole ? whole->bytes() : 0);
}

// ---------------------------------------------------------------------------
// Bake down
// ---------------------------------------------------------------------------

bool microBakeMesh(const Mesh& m, int level, Mesh& out, std::string& error, size_t maxTriangles) {
    if (!m.micro || !microMatches(m)) {
        error = "This Part has no micro level";
        return false;
    }
    const MicroMesh& mm = *m.micro;
    if (level < 0 || level > mm.level) level = mm.level;
    if (mm.edgeNeighbor.size() != size_t(mm.baseTriangles) * 3) {
        error = "Micro level topology missing";
        return false;
    }
    if (maxTriangles == 0) maxTriangles = subdivMaxTriangles();
    const uint32_t q = 1u << level, step = mm.n / q, nt = mm.baseTriangles, nv = mm.baseVertices;
    const size_t tris = size_t(nt) * q * q;
    if (tris > maxTriangles || tris >= (size_t(1) << 32)) {
        char buf[200];
        std::snprintf(buf, sizeof buf, "Baking micro level %d makes %.0fM triangles, more than this computer allows (%.0fM): pick a lower level",
                      level, double(tris) / 1e6, double(maxTriangles) / 1e6);
        error = buf;
        return false;
    }
    // Vertex numbering: base vertices, then each base edge's q - 1 inner points (numbered by the triangle that
    // owns the edge: the lower index of the two), then each triangle's inner points.
    std::vector<uint32_t> edgeStart(size_t(nt) * 3, 0);
    uint32_t next = nv;
    for (uint32_t t = 0; t < nt; ++t)
        for (int e = 0; e < 3; ++e) {
            const uint32_t nb = mm.edgeNeighbor[size_t(t) * 3 + size_t(e)];
            if (nb == MicroMesh::kNone || (nb >> 2) > t) {
                edgeStart[size_t(t) * 3 + size_t(e)] = next;
                next += q - 1;
            }
        }
    for (uint32_t t = 0; t < nt; ++t)
        for (int e = 0; e < 3; ++e) {
            const uint32_t nb = mm.edgeNeighbor[size_t(t) * 3 + size_t(e)];
            if (nb != MicroMesh::kNone && (nb >> 2) < t) edgeStart[size_t(t) * 3 + size_t(e)] = edgeStart[size_t(nb >> 2) * 3 + (nb & 3)];
        }
    const uint32_t inner = q >= 2 ? (q - 1) * (q - 2) / 2 : 0;
    const size_t verts = size_t(next) + size_t(nt) * inner;
    if (verts >= (size_t(1) << 32)) {
        error = "Too many vertices";
        return false;
    }
    out = Mesh();
    out.positions.resize(verts);
    out.triangles.resize(tris);
    const bool uvs = m.hasUvs(), groups = m.hasFaceGroups(), hidden = m.hasHidden(), masked = mm.hasMask();
    if (uvs) out.uvs.resize(tris * 3);
    if (groups) out.facegroups.resize(tris);
    if (hidden) out.hidden.resize(tris);
    if (masked) out.mask.assign(verts, 0.0f);
    // The vertex of grid point (a, b) (bake level) of triangle t.
    auto vertexOf = [&](uint32_t t, uint32_t a, uint32_t b) -> uint32_t {
        const glm::uvec3 tr = m.triangles[t];
        if (a == 0 && b == 0) return tr.x;
        if (a == q && b == 0) return tr.y;
        if (a == 0 && b == q) return tr.z;
        int e = -1;
        uint32_t k = 0;
        if (b == 0) e = 0, k = a;
        else if (a + b == q) e = 1, k = b;
        else if (a == 0) e = 2, k = q - b;
        if (e >= 0) {
            const uint32_t nb = mm.edgeNeighbor[size_t(t) * 3 + size_t(e)];
            const bool owner = nb == MicroMesh::kNone || (nb >> 2) > t;
            if (!owner) { // numbered from the owner's start corner
                const uint32_t u = nb >> 2;
                const bool reversed = m.triangles[u][nb & 3] != tr[e];
                if (reversed) k = q - k;
            }
            return edgeStart[size_t(t) * 3 + size_t(e)] + k - 1;
        }
        // inner point: rows b = 1..q-2, a = 1..q-1-b
        const uint32_t r = b - 1;
        const uint32_t before = r * (q - 2) - r * (r - 1) / 2; // points in rows 1..b-1: sum (q - 1 - b')
        return next + t * inner + before + (a - 1);
    };
    poolFor(nt, [&](size_t b0, size_t e0) {
        MicroTriangle T;
        for (size_t tt = b0; tt < e0; ++tt) {
            const uint32_t t = uint32_t(tt);
            T.set(m, t, mm.n);
            const int16_t* g = mm.disp.data() + size_t(t) * mm.samples;
            const uint8_t* mk = masked ? mm.mask.data() + size_t(t) * mm.samples : nullptr;
            for (uint32_t b = 0; b <= q; ++b)
                for (uint32_t a = 0; a + b <= q; ++a) {
                    const uint32_t v = vertexOf(t, a, b);
                    // Each shared point is written by every triangle holding it, with the same value (stitched).
                    const uint32_t i = a * step, j = b * step, idx = MicroMesh::index(i, j, mm.n);
                    glm::vec3 s, nn;
                    T.eval(i, j, s, nn);
                    out.positions[v] = s + nn * (float(g[idx]) * mm.step);
                    if (mk) out.mask[v] = float(mk[idx]) / 255.0f;
                }
            const size_t first = size_t(t) * q * q;
            size_t o = first;
            glm::vec2 uv[3];
            if (uvs) uv[0] = m.uvs[size_t(t) * 3], uv[1] = m.uvs[size_t(t) * 3 + 1], uv[2] = m.uvs[size_t(t) * 3 + 2];
            auto uvAt = [&](uint32_t a, uint32_t b) {
                const float fa = float(a) / float(q), fb = float(b) / float(q);
                return uv[0] * (1.0f - fa - fb) + uv[1] * fa + uv[2] * fb;
            };
            for (uint32_t b = 0; b < q; ++b)
                for (uint32_t a = 0; a + b < q; ++a) {
                    out.triangles[o] = {vertexOf(t, a, b), vertexOf(t, a + 1, b), vertexOf(t, a, b + 1)};
                    if (uvs) out.uvs[o * 3] = uvAt(a, b), out.uvs[o * 3 + 1] = uvAt(a + 1, b), out.uvs[o * 3 + 2] = uvAt(a, b + 1);
                    ++o;
                    if (a + b + 1 < q) {
                        out.triangles[o] = {vertexOf(t, a + 1, b), vertexOf(t, a + 1, b + 1), vertexOf(t, a, b + 1)};
                        if (uvs)
                            out.uvs[o * 3] = uvAt(a + 1, b), out.uvs[o * 3 + 1] = uvAt(a + 1, b + 1), out.uvs[o * 3 + 2] = uvAt(a, b + 1);
                        ++o;
                    }
                }
            for (size_t k = first; k < o; ++k) {
                if (groups) out.facegroups[k] = m.facegroups[t];
                if (hidden) out.hidden[k] = m.hidden[t];
            }
        }
    }, 256);
    out.texture = m.texture;
    out.paintToTexture = m.paintToTexture;
    out.rebuildTopology();
    out.recomputeAllNormals();
    return true;
}

// ---------------------------------------------------------------------------
// Displacement maps
// ---------------------------------------------------------------------------

bool microExportDisplacement(const Mesh& m, const std::string& path, int size, bool vector, const std::string& format,
                             float& scaleOut, std::string& error) {
    if (!m.micro || !microMatches(m)) {
        error = "This Part has no micro level";
        return false;
    }
    if (!m.hasUvs()) {
        error = "Displacement maps need UVs on the base (Tool > UV Map, at the lowest level)";
        return false;
    }
    if (size < 16 || size > 16384) {
        error = "Map size must be 16 to 16384";
        return false;
    }
    if (format != "exr" && format != "png") {
        error = "Format must be exr or png";
        return false;
    }
    const MicroMesh& mm = *m.micro;
    const int W = size, H = size, C = vector ? 3 : 1;
    std::vector<float> px(size_t(W) * H * C, 0.0f);
    std::vector<uint8_t> covered(size_t(W) * H, 0);
    const uint32_t n = mm.n, S = mm.samples;
    poolFor(mm.baseTriangles, [&](size_t b0, size_t e0) {
        MicroTriangle T;
        thread_local std::vector<glm::vec3> P, F, N;
        P.resize(S), F.resize(S), N.resize(S);
        for (size_t tt = b0; tt < e0; ++tt) {
            const uint32_t t = uint32_t(tt);
            if (m.triangleHidden(t)) continue;
            const glm::vec2 a = m.uvs[size_t(t) * 3], b = m.uvs[size_t(t) * 3 + 1], c = m.uvs[size_t(t) * 3 + 2];
            // texel space, top-down
            const glm::vec2 A(a.x * W, (1.0f - a.y) * H), B(b.x * W, (1.0f - b.y) * H), Cc(c.x * W, (1.0f - c.y) * H);
            const float area = (B.x - A.x) * (Cc.y - A.y) - (Cc.x - A.x) * (B.y - A.y);
            if (std::abs(area) < 1e-12f) continue;
            T.set(m, t, n);
            const int16_t* g = mm.disp.data() + size_t(t) * S;
            uint32_t idx = 0;
            for (uint32_t j = 0; j <= n; ++j)
                for (uint32_t i = 0; i + j <= n; ++i, ++idx) {
                    glm::vec3 s, nn;
                    T.eval(i, j, s, nn);
                    P[idx] = s + nn * (float(g[idx]) * mm.step);
                    F[idx] = T.flat(i, j);
                    N[idx] = nn;
                }
            const int x0 = std::max(0, int(std::floor(std::min({A.x, B.x, Cc.x})))),
                      x1 = std::min(W - 1, int(std::ceil(std::max({A.x, B.x, Cc.x})))),
                      y0 = std::max(0, int(std::floor(std::min({A.y, B.y, Cc.y})))),
                      y1 = std::min(H - 1, int(std::ceil(std::max({A.y, B.y, Cc.y}))));
            for (int y = y0; y <= y1; ++y)
                for (int x = x0; x <= x1; ++x) {
                    const glm::vec2 p(float(x) + 0.5f, float(y) + 0.5f);
                    const float w1 = ((p.x - A.x) * (Cc.y - A.y) - (Cc.x - A.x) * (p.y - A.y)) / area;
                    const float w2 = ((B.x - A.x) * (p.y - A.y) - (p.x - A.x) * (B.y - A.y)) / area;
                    const float w0 = 1.0f - w1 - w2;
                    if (w0 < -1e-5f || w1 < -1e-5f || w2 < -1e-5f) continue;
                    const float w[3] = {w0, w1, w2};
                    const Cell cl = cellAt(w, n);
                    glm::vec3 pm(0.0f), pf(0.0f), pn(0.0f);
                    for (int k = 0; k < 3; ++k) {
                        const uint32_t id = MicroMesh::index(cl.i[k], cl.j[k], n);
                        pm += P[id] * cl.w[k], pf += F[id] * cl.w[k], pn += N[id] * cl.w[k];
                    }
                    const size_t o = size_t(y) * W + size_t(x);
                    const glm::vec3 off = pm - pf;
                    if (vector) px[o * 3] = off.x, px[o * 3 + 1] = off.y, px[o * 3 + 2] = off.z;
                    else px[o] = glm::dot(off, glm::normalize(pn));
                    covered[o] = 1;
                }
        }
    }, 256);
    // Padding: 8 rings of texels around the islands take their neighbours' values (mip and filter seams).
    for (int pass = 0; pass < 8; ++pass) {
        std::vector<uint8_t> grow = covered;
        for (int y = 0; y < H; ++y)
            for (int x = 0; x < W; ++x) {
                const size_t o = size_t(y) * W + size_t(x);
                if (covered[o]) continue;
                float sum[3] = {0, 0, 0};
                int cnt = 0;
                for (int dy = -1; dy <= 1; ++dy)
                    for (int dx = -1; dx <= 1; ++dx) {
                        const int xx = x + dx, yy = y + dy;
                        if (xx < 0 || yy < 0 || xx >= W || yy >= H) continue;
                        const size_t q = size_t(yy) * W + size_t(xx);
                        if (!covered[q]) continue;
                        for (int k = 0; k < C; ++k) sum[k] += px[q * C + size_t(k)];
                        ++cnt;
                    }
                if (!cnt) continue;
                for (int k = 0; k < C; ++k) px[o * C + size_t(k)] = sum[k] / float(cnt);
                grow[o] = 1;
            }
        covered.swap(grow);
    }
    float maxAbs = 0.0f;
    for (float v : px) maxAbs = std::max(maxAbs, std::abs(v));
    scaleOut = maxAbs;
    if (format == "exr") return saveExr(path, W, H, C, px, error);
    std::vector<uint16_t> q(px.size());
    const float s = maxAbs > 0.0f ? 32767.0f / maxAbs : 0.0f;
    for (size_t i = 0; i < px.size(); ++i) q[i] = uint16_t(std::clamp(std::lround(px[i] * s) + 32768L, 0L, 65535L));
    return savePng16(path, W, H, C, q, error);
}

// ---------------------------------------------------------------------------
// Procedural detail
// ---------------------------------------------------------------------------

namespace {

float hashFloat(int x, int y, int z, uint32_t seed) {
    uint32_t h = uint32_t(x) * 0x8da6b343u ^ uint32_t(y) * 0xd8163841u ^ uint32_t(z) * 0xcb1ab31fu ^ seed * 0x9E3779B9u;
    h ^= h >> 13;
    h *= 0x85EBCA6Bu;
    h ^= h >> 16;
    return float(h & 0xFFFFFF) / float(0xFFFFFF) * 2.0f - 1.0f;
}

float valueNoise(const glm::vec3& p, uint32_t seed) {
    const glm::vec3 f = glm::floor(p);
    const glm::vec3 t = p - f;
    const glm::vec3 u = t * t * (3.0f - 2.0f * t);
    const int x = int(f.x), y = int(f.y), z = int(f.z);
    auto h = [&](int dx, int dy, int dz) { return hashFloat(x + dx, y + dy, z + dz, seed); };
    const float a = glm::mix(glm::mix(h(0, 0, 0), h(1, 0, 0), u.x), glm::mix(h(0, 1, 0), h(1, 1, 0), u.x), u.y);
    const float b = glm::mix(glm::mix(h(0, 0, 1), h(1, 0, 1), u.x), glm::mix(h(0, 1, 1), h(1, 1, 1), u.x), u.y);
    return glm::mix(a, b, u.z);
}

} // namespace

void microNoise(Mesh& m, float amplitude, float frequency, uint32_t seed) {
    if (!m.micro) return;
    MicroMesh& mm = mutableMicro(m);
    mm.ensureTopology(m);
    mm.widen(float(mm.rangeMax) * mm.step + std::abs(amplitude) * 1.5f);
    const uint32_t n = mm.n, S = mm.samples;
    poolFor(mm.baseTriangles, [&](size_t b0, size_t e0) {
        MicroTriangle T;
        for (size_t tt = b0; tt < e0; ++tt) {
            const uint32_t t = uint32_t(tt);
            if (m.triangleHidden(t)) continue;
            T.set(m, t, n);
            int16_t* g = mm.disp.data() + size_t(t) * S;
            const uint8_t* mk = mm.hasMask() ? mm.mask.data() + size_t(t) * S : nullptr;
            uint32_t idx = 0;
            int r = mm.triRange[t];
            for (uint32_t j = 0; j <= n; ++j)
                for (uint32_t i = 0; i + j <= n; ++i, ++idx) {
                    glm::vec3 s, nn;
                    T.eval(i, j, s, nn);
                    const glm::vec3 p = s * frequency;
                    // three octaves, ridged a little so it reads as skin-like pores and wrinkles
                    float v = valueNoise(p, seed) * 0.6f + valueNoise(p * 2.03f, seed + 1) * 0.28f +
                              valueNoise(p * 4.11f, seed + 2) * 0.12f;
                    v = 1.0f - std::abs(v) * 2.0f;
                    float d = float(g[idx]) * mm.step + amplitude * v * (mk ? 1.0f - float(mk[idx]) / 255.0f : 1.0f);
                    const long q = std::clamp(std::lround(d / mm.step), -32767L, 32767L);
                    g[idx] = int16_t(q);
                    r = std::max(r, int(std::abs(q)));
                }
            mm.triRange[t] = uint16_t(r);
        }
    }, 256);
    for (uint16_t r : mm.triRange) mm.rangeMax = std::max(mm.rangeMax, r);
    mm.markAllDirty();
    ++mm.revision;
}

} // namespace sf