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.

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

#include "core/Commands.h"
#include "core/Document.h"
#include "core/IndexBits.h"
#include "core/ThreadPool.h"

#include <algorithm>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <filesystem>
#include <fstream>
#include <sstream>

namespace sf {

namespace {

using Clock = std::chrono::steady_clock;

double unixNow() {
    return std::chrono::duration<double>(std::chrono::system_clock::now().time_since_epoch()).count();
}

// Shared scratch set for a seek's moved vertices (one seek at a time: the main thread).
IndexBits& batchBits() {
    static IndexBits bits;
    return bits;
}

void gather(const std::vector<glm::vec3>& from, const std::vector<uint32_t>& idx, std::vector<glm::vec3>& out) {
    out.resize(idx.size());
    poolFor(idx.size(), [&](size_t b, size_t e) {
        for (size_t i = b; i < e; ++i) out[i] = from[idx[i]];
    }, 1 << 14);
}

void scatter(std::vector<glm::vec3>& to, const std::vector<uint32_t>& idx, const std::vector<glm::vec3>& values) {
    poolFor(idx.size(), [&](size_t b, size_t e) {
        for (size_t i = b; i < e; ++i) to[idx[i]] = values[i];
    }, 1 << 14);
}

size_t vecBytes(const std::vector<glm::vec3>& v) { return v.capacity() * sizeof(glm::vec3); }

} // namespace

// ---------------------------------------------------------------------------------------------------------------
// The tree

Timeline::Kind Timeline::classify(const UndoRecord& r) {
    if (r.subdiv || r.mesh || r.topology || r.part) return Kind::Topology;
    if (!r.positions.empty()) return Kind::Stroke;
    if (!r.mask.empty()) return Kind::Mask;
    if (!r.colors.empty() || r.paint || r.texture || r.textureTiles) return Kind::Paint;
    if (!r.hidden.empty() || !r.facegroups.empty()) return Kind::Visibility;
    return Kind::Other;
}

bool Timeline::fastShape(const UndoRecord& r) {
    return !r.positions.empty() && r.layer == -1 && r.layerOffsets.empty() && r.mask.empty() && r.colors.empty() &&
           r.paintAlpha.empty() && !r.paint && r.hidden.empty() && r.facegroups.empty() && !r.textureTiles &&
           !r.texture && !r.mesh && !r.subdiv && !r.topology && !r.part && !r.uv;
}

void Timeline::reset() {
    nodes_.clear();
    checkpoints_.clear();
    nodes_.emplace_back();
    nodes_[0].kind = Kind::Start;
    nodes_[0].label = "Start";
    nodes_[0].time = unixNow();
    path_.assign(1, 0);
    cursor_ = 0;
}

uint32_t Timeline::newNode(uint32_t parent, const UndoRecord* r) {
    const uint32_t id = uint32_t(nodes_.size());
    nodes_.emplace_back();
    Node& n = nodes_.back();
    n.parent = parent;
    n.time = unixNow();
    if (r) {
        n.label = r->label.empty() ? "Edit" : r->label;
        n.kind = classify(*r);
        n.touched = uint32_t(std::max({r->positions.indices.size(), r->mask.indices.size(), r->colors.indices.size(),
                                       r->hidden.indices.size(), r->facegroups.indices.size()}));
    }
    if (parent != kNone) {
        nodes_[parent].children.push_back(id);
        nodes_[parent].activeChild = id;
    }
    return id;
}

std::shared_ptr<Timeline> Timeline::attach(Document& doc) {
    auto t = std::make_shared<Timeline>();
    t->reset();
    t->stack_ = &doc.undo;
    UndoStack& s = doc.undo;
    for (UndoRecord& r : s.undo_) t->path_.push_back(t->newNode(t->path_.back(), &r));
    t->cursor_ = s.undo_.size();
    for (auto it = s.redo_.rbegin(); it != s.redo_.rend(); ++it) t->path_.push_back(t->newNode(t->path_.back(), &*it));
    // Back to the cursor's branch: newNode made each new node its parent's active child already.
    doc.undo.listener = t;
    t->sync(doc);
    return t;
}

Timeline* Timeline::of(UndoStack& stack) { return dynamic_cast<Timeline*>(stack.listener.get()); }

bool Timeline::onPath(uint32_t id) const {
    if (id >= nodes_.size() || !nodes_[id].alive) return false;
    const int d = depth(id);
    return d >= 0 && size_t(d) < path_.size() && path_[size_t(d)] == id;
}

int Timeline::depth(uint32_t id) const {
    if (id >= nodes_.size()) return -1;
    int d = 0;
    for (uint32_t p = nodes_[id].parent; p != kNone; p = nodes_[p].parent) ++d;
    return d;
}

size_t Timeline::aliveCount() const {
    size_t n = 0;
    for (const Node& x : nodes_) n += x.alive;
    return n;
}

std::vector<Timeline::Branch> Timeline::branches() const {
    std::vector<Branch> out;
    for (size_t i = 0; i < path_.size(); ++i) {
        const Node& p = nodes_[path_[i]];
        for (uint32_t c : p.children) {
            if (!nodes_[c].alive || (i + 1 < path_.size() && path_[i + 1] == c)) continue;
            Branch b{c, i, 1, c};
            while (nodes_[b.tip].activeChild != kNone && nodes_[nodes_[b.tip].activeChild].alive) {
                b.tip = nodes_[b.tip].activeChild;
                ++b.length;
            }
            out.push_back(b);
        }
    }
    return out;
}

UndoRecord* Timeline::recordOf(uint32_t id) {
    if (id >= nodes_.size() || !nodes_[id].alive || nodes_[id].parent == kNone) return nullptr;
    if (nodes_[id].stored) return nodes_[id].stored.get();
    if (!stack_) return nullptr;
    const int d = depth(id);
    if (d <= 0 || size_t(d) >= path_.size() || path_[size_t(d)] != id) return nullptr;
    const size_t i = size_t(d);
    if (i <= cursor_) return i - 1 < stack_->undo_.size() ? &stack_->undo_[i - 1] : nullptr;
    const size_t k = i - cursor_ - 1; // 0 = the next redo
    return k < stack_->redo_.size() ? &stack_->redo_[stack_->redo_.size() - 1 - k] : nullptr;
}

void Timeline::freeSubtree(uint32_t id) {
    std::vector<uint32_t> todo{id};
    while (!todo.empty()) {
        const uint32_t x = todo.back();
        todo.pop_back();
        Node& n = nodes_[x];
        for (uint32_t c : n.children) todo.push_back(c);
        n.alive = false;
        n.children.clear();
        n.activeChild = kNone;
        n.stored.reset();
        std::vector<glm::vec3>().swap(n.other);
        std::vector<glm::vec3>().swap(n.retuneDelta);
        n.fast = false;
        checkpoints_.erase(x);
    }
    const uint32_t p = nodes_[id].parent;
    if (p != kNone) {
        auto& ch = nodes_[p].children;
        ch.erase(std::remove(ch.begin(), ch.end(), id), ch.end());
        if (nodes_[p].activeChild == id) nodes_[p].activeChild = ch.empty() ? kNone : ch.back();
    }
}

// ---------------------------------------------------------------------------------------------------------------
// Following the undo stack

void Timeline::undoPushed(UndoRecord& pushed, std::deque<UndoRecord>& discardedRedo) {
    // The redo steps become an inactive branch: redo.back() is path_[cursor_ + 1].
    const size_t n = discardedRedo.size();
    for (size_t k = 0; k < n && cursor_ + 1 + k < path_.size(); ++k)
        nodes_[path_[cursor_ + 1 + k]].stored = std::make_unique<UndoRecord>(std::move(discardedRedo[n - 1 - k]));
    path_.resize(cursor_ + 1);
    path_.push_back(newNode(path_.back(), &pushed));
    ++cursor_;
    enforceBudgets();
}

void Timeline::captureFrom(Node& n, const UndoRecord& r, Mesh& mesh) {
    n.captured = true;
    const auto& idx = r.positions.indices;
    uint32_t maxIndex = 0;
    for (uint32_t v : idx) maxIndex = std::max(maxIndex, v);
    if (idx.empty() || maxIndex >= mesh.vertexCount()) return;
    glm::vec3 lo(1e30f), hi(-1e30f); // bounds of the stroke after it
    for (uint32_t v : idx) {
        lo = glm::min(lo, mesh.positions[v]);
        hi = glm::max(hi, mesh.positions[v]);
    }
    n.center = (lo + hi) * 0.5f;
    n.radius = glm::length(hi - lo) * 0.5f;
    if (fastShape(r) && mesh.layers.empty()) {
        gather(mesh.positions, idx, n.other);
        n.fast = true;
    }
}

void Timeline::capture(Mesh& mesh) {
    if (cursor_ == 0 || cursor_ >= path_.size() || !stack_ || cursor_ - 1 >= stack_->undo_.size()) return;
    captureFrom(nodes_[path_[cursor_]], stack_->undo_[cursor_ - 1], mesh);
}

void Timeline::undoApplying(UndoRecord& r, Mesh& mesh, bool isUndo) {
    // A step about to be undone: bring its "after" values in while the mesh still shows them.
    if (isUndo && cursor_ > 0 && !nodes_[path_[cursor_]].captured) captureFrom(nodes_[path_[cursor_]], r, mesh);
}

void Timeline::undoApplied(UndoRecord& r, Mesh& mesh, bool isUndo) {
    if (isUndo) {
        if (cursor_ == 0) return;
        Node& n = nodes_[path_[cursor_]];
        if (n.fast) {
            if (mesh.layers.empty() && fastShape(r)) gather(mesh.positions, r.positions.indices, n.other); // now "before"
            else n.fast = false, std::vector<glm::vec3>().swap(n.other);
        }
        --cursor_;
    } else {
        if (cursor_ + 1 >= path_.size()) return;
        ++cursor_;
        Node& n = nodes_[path_[cursor_]];
        if (!n.captured) {
            captureFrom(n, r, mesh);
        } else if (mesh.layers.empty() && fastShape(r)) {
            gather(mesh.positions, r.positions.indices, n.other); // "after"
            n.fast = true;
        } else {
            n.fast = false;
            std::vector<glm::vec3>().swap(n.other);
        }
    }
}

void Timeline::undoDroppedOldest() {
    if (path_.size() < 2) return;
    const uint32_t oldRoot = path_[0], newRoot = path_[1];
    for (uint32_t c : std::vector<uint32_t>(nodes_[oldRoot].children))
        if (c != newRoot) freeSubtree(c);
    Node& o = nodes_[oldRoot];
    o.alive = false;
    o.children.clear();
    checkpoints_.erase(oldRoot);
    Node& n = nodes_[newRoot];
    n.parent = kNone;
    n.stored.reset();
    n.fast = false;
    std::vector<glm::vec3>().swap(n.other);
    std::vector<glm::vec3>().swap(n.retuneDelta);
    path_.erase(path_.begin());
    if (cursor_ > 0) --cursor_;
}

void Timeline::undoCleared() { reset(); }

void Timeline::sync(Document& doc) {
    stack_ = &doc.undo;
    if (doc.undo.listener.get() != this) return;
    // The stack and the tree should always agree; if something replaced the stack's steps behind our back,
    // start over from what the stack holds.
    if (path_.size() != doc.undo.undo_.size() + doc.undo.redo_.size() + 1 || cursor_ != doc.undo.undo_.size()) {
        reset();
        for (UndoRecord& r : doc.undo.undo_) path_.push_back(newNode(path_.back(), &r));
        cursor_ = doc.undo.undo_.size();
        for (auto it = doc.undo.redo_.rbegin(); it != doc.undo.redo_.rend(); ++it)
            path_.push_back(newNode(path_.back(), &*it));
    }
    if (cursor_ > 0) {
        Node& n = nodes_[path_[cursor_]];
        if (!n.captured) capture(doc.mesh);
    }
    maybeCheckpoint(doc.mesh);
}

// ---------------------------------------------------------------------------------------------------------------
// Checkpoints and budgets

size_t Timeline::checkpointBytes() const {
    size_t b = 0;
    for (const auto& [id, c] : checkpoints_) b += vecBytes(c);
    return b;
}

size_t Timeline::extraBytes() const {
    size_t b = 0;
    for (const Node& n : nodes_) {
        if (!n.alive) continue;
        b += vecBytes(n.other) + vecBytes(n.retuneDelta);
        if (n.stored) b += n.stored->approxBytes();
    }
    return b;
}

void Timeline::maybeCheckpoint(const Mesh& mesh) {
    const uint32_t id = path_[cursor_];
    if (checkpoints_.count(id) || cursor_ % std::max<size_t>(checkpointEvery, 1) != 0 || !mesh.layers.empty() ||
        mesh.vertexCount() == 0)
        return;
    if (cursor_ > 0 && !nodes_[id].fast) return; // a checkpoint helps runs of fast steps
    const size_t bytes = mesh.vertexCount() * sizeof(glm::vec3);
    if (bytes > checkpointBudget) return;
    std::vector<glm::vec3> copy(mesh.vertexCount());
    poolFor(copy.size(), [&](size_t b, size_t e) { std::memcpy(&copy[b], &mesh.positions[b], (e - b) * sizeof(glm::vec3)); },
            1 << 18);
    checkpoints_[id] = std::move(copy);
    enforceBudgets();
}

void Timeline::enforceBudgets() {
    // Checkpoints: thin them out by doubling the interval, then drop the deepest ones off the active branch.
    while (checkpointBytes() > checkpointBudget && !checkpoints_.empty()) {
        checkpointEvery = std::max<size_t>(checkpointEvery, 1) * 2;
        bool dropped = false;
        for (auto it = checkpoints_.begin(); it != checkpoints_.end();) {
            const int d = depth(it->first);
            if (d > 0 && size_t(d) % checkpointEvery != 0) {
                it = checkpoints_.erase(it);
                dropped = true;
            } else {
                ++it;
            }
        }
        if (!dropped && checkpointBytes() > checkpointBudget) {
            // Even the multiples don't fit: keep the shallowest.
            uint32_t deepest = checkpoints_.begin()->first;
            for (const auto& [id, c] : checkpoints_)
                if (depth(id) > depth(deepest)) deepest = id;
            checkpoints_.erase(deepest);
        }
    }
    // Inactive branches and `other` copies: the oldest branches go first, then the oldest steps' copies (those
    // steps are then walked by the undo stack instead).
    size_t extra = extraBytes();
    if (extra <= branchBudget) return;
    std::vector<Branch> bs = branches();
    std::sort(bs.begin(), bs.end(), [&](const Branch& a, const Branch& b) { return nodes_[a.first].time < nodes_[b.first].time; });
    for (const Branch& b : bs) {
        if (extra <= branchBudget) break;
        freeSubtree(b.first);
        extra = extraBytes();
    }
    for (size_t i = 1; i < path_.size() && extra > branchBudget; ++i) {
        Node& n = nodes_[path_[i]];
        if (!n.fast) continue;
        extra -= std::min(extra, vecBytes(n.other));
        n.fast = false;
        std::vector<glm::vec3>().swap(n.other);
    }
}

// ---------------------------------------------------------------------------------------------------------------
// Travel

void Timeline::flushBatch(Document& doc) {
    if (batch_.empty()) return;
    const auto t0 = Clock::now();
    struct Done {
        Clock::time_point t0;
        double& ms;
        ~Done() { ms += std::chrono::duration<double, std::milli>(Clock::now() - t0).count(); }
    } done{t0, flushMs_};
    Mesh& mesh = doc.mesh;
    IndexBits& bits = batchBits();
    if (bits.capacity() < mesh.vertexCount()) bits.resize(mesh.vertexCount());
    std::vector<uint32_t> verts;
    for (uint32_t v : batch_) bits.insertLocal(v);
    bits.take(verts);
    batch_.clear();
    // Normals: the parallel update unless nearly everything moved (Mesh::recomputeAllNormals sums serially).
    if (verts.size() * 10 > mesh.vertexCount() * 9) mesh.recomputeAllNormals();
    else mesh.updateNormals(verts);
    // Refits only grow boxes: after moving much of the mesh, tighten the whole tree (as UndoStack::apply does).
    if (verts.size() * 4 > mesh.vertexCount()) doc.bvh.refitAll(mesh);
    else doc.bvh.refit(mesh, verts);
}

namespace {
bool fastUsable(const Timeline::Node& n, const UndoRecord* r, const Mesh& mesh) {
    if (!n.fast || !r || !Timeline::fastShape(*r) || !mesh.layers.empty()) return false;
    if (n.other.size() != r->positions.indices.size()) return false;
    for (uint32_t v : r->positions.indices) // (cheap next to the copy below)
        if (v >= mesh.vertexCount()) return false;
    return true;
}
} // namespace

void Timeline::walkTo(Document& doc, size_t index) {
    UndoStack& s = doc.undo;
    Mesh& mesh = doc.mesh;
    while (cursor_ > index) {
        Node& n = nodes_[path_[cursor_]];
        UndoRecord* r = s.undo_.empty() ? nullptr : &s.undo_.back();
        if (fastUsable(n, r, mesh)) {
            scatter(mesh.positions, r->positions.indices, r->positions.values); // "before"
            std::swap(r->positions.values, n.other);                           // the record now holds "after"
            batch_.insert(batch_.end(), r->positions.indices.begin(), r->positions.indices.end());
            s.redo_.push_back(std::move(*r));
            s.undo_.pop_back();
            ++s.revision_;
            --cursor_;
            ++lastSeek_.batched;
        } else {
            flushBatch(doc);
            if (!s.undo(mesh, doc.bvh)) break;
            if (UndoRecord* u = s.lastRedo(); u && u->part) doc.applyPartStep(*u->part);
            ++lastSeek_.walked;
        }
    }
    while (cursor_ < index) {
        Node& n = nodes_[path_[cursor_ + 1]];
        UndoRecord* r = s.redo_.empty() ? nullptr : &s.redo_.back();
        if (fastUsable(n, r, mesh)) {
            scatter(mesh.positions, r->positions.indices, r->positions.values); // "after"
            std::swap(r->positions.values, n.other);
            batch_.insert(batch_.end(), r->positions.indices.begin(), r->positions.indices.end());
            s.undo_.push_back(std::move(*r));
            s.redo_.pop_back();
            ++s.revision_;
            ++cursor_;
            ++lastSeek_.batched;
        } else {
            flushBatch(doc);
            if (!s.redo(mesh, doc.bvh)) break;
            if (UndoRecord* u = s.lastUndo(); u && u->part) doc.applyPartStep(*u->part);
            ++lastSeek_.walked;
        }
    }
    flushBatch(doc);
}

bool Timeline::jumpWithCheckpoint(Document& doc, size_t index) {
    Mesh& mesh = doc.mesh;
    const size_t V = mesh.vertexCount();
    if (checkpoints_.empty() || index == cursor_ || !mesh.layers.empty()) return false;
    const size_t lo = std::min(index, cursor_), hi = std::max(index, cursor_);
    auto fastAt = [&](size_t i) { return fastUsable(nodes_[path_[i]], recordOf(path_[i]), mesh); };
    size_t walkCost = 0;
    for (size_t i = lo + 1; i <= hi; ++i) {
        if (!fastAt(i)) return false; // a slow step in between: walk
        walkCost += nodes_[path_[i]].other.size();
    }
    // The nearest usable checkpoint at or before the target.
    size_t from = std::string::npos, replayCost = 0;
    for (size_t p = index + 1; p-- > 0;) {
        if (p < index && !fastAt(p + 1)) break;
        if (p < index) replayCost += nodes_[path_[p + 1]].other.size();
        auto it = checkpoints_.find(path_[p]);
        if (it != checkpoints_.end() && it->second.size() == V) {
            from = p;
            break;
        }
        if (replayCost + V >= walkCost) return false;
    }
    if (from == std::string::npos || V + replayCost >= walkCost) return false;
    const std::vector<glm::vec3>& ck = checkpoints_[path_[from]];
    poolFor(V, [&](size_t b, size_t e) { std::memcpy(&mesh.positions[b], &ck[b], (e - b) * sizeof(glm::vec3)); }, 1 << 18);
    for (size_t j = from + 1; j <= index; ++j) {
        Node& n = nodes_[path_[j]];
        const UndoRecord* r = recordOf(path_[j]);
        scatter(mesh.positions, r->positions.indices, j <= cursor_ ? n.other : r->positions.values); // "after" values
        ++lastSeek_.replayed;
    }
    // The steps between move sides without touching the mesh: swap which vector the record holds.
    UndoStack& s = *stack_;
    while (cursor_ > index) {
        UndoRecord& r = s.undo_.back();
        std::swap(r.positions.values, nodes_[path_[cursor_]].other);
        s.redo_.push_back(std::move(r));
        s.undo_.pop_back();
        --cursor_;
    }
    while (cursor_ < index) {
        UndoRecord& r = s.redo_.back();
        std::swap(r.positions.values, nodes_[path_[cursor_ + 1]].other);
        s.undo_.push_back(std::move(r));
        s.redo_.pop_back();
        ++cursor_;
    }
    ++s.revision_;
    // Normals, the BVH and the GPU: only where the shape changed (the steps between the old and the new cursor).
    for (size_t j = lo + 1; j <= hi; ++j) {
        const UndoRecord* r = recordOf(path_[j]);
        batch_.insert(batch_.end(), r->positions.indices.begin(), r->positions.indices.end());
    }
    flushBatch(doc);
    lastSeek_.usedCheckpoint = true;
    return true;
}

bool Timeline::seek(Document& doc, size_t index, std::string* error) {
    if (doc.undo.listener.get() != this) {
        if (error) *error = "This timeline doesn't watch the document's history";
        return false;
    }
    sync(doc);
    if (index >= path_.size()) {
        if (error) *error = "No step " + std::to_string(index) + " on this branch (it has " + std::to_string(path_.size() - 1) + ")";
        return false;
    }
    const auto t0 = Clock::now();
    lastSeek_ = {};
    if (!jumpWithCheckpoint(doc, index)) walkTo(doc, index);
    lastSeek_.ms = std::chrono::duration<double, std::milli>(Clock::now() - t0).count();
    sync(doc);
    if (std::getenv("SF_TIMELINE_LOG"))
        std::fprintf(stderr, "timeline seek to %zu: %.1f ms (flush %.1f ms), then sync %.1f ms\n", index, lastSeek_.ms,
                     flushMs_, std::chrono::duration<double, std::milli>(Clock::now() - t0).count() - lastSeek_.ms);
    flushMs_ = 0.0;
    if (cursor_ != index) {
        if (error) *error = "Stopped at step " + std::to_string(cursor_);
        return false;
    }
    return true;
}

bool Timeline::select(Document& doc, uint32_t id, std::string* error) {
    if (doc.undo.listener.get() != this) {
        if (error) *error = "This timeline doesn't watch the document's history";
        return false;
    }
    sync(doc);
    if (id >= nodes_.size() || !nodes_[id].alive) {
        if (error) *error = "No such step";
        return false;
    }
    if (onPath(id)) return seek(doc, size_t(depth(id)), error);
    std::vector<uint32_t> chain; // from the branch's first node to `id`
    uint32_t a = id;
    while (a != kNone && !onPath(a)) {
        chain.push_back(a);
        a = nodes_[a].parent;
    }
    if (a == kNone) {
        if (error) *error = "That step isn't connected to the history any more";
        return false;
    }
    std::reverse(chain.begin(), chain.end());
    const size_t ap = size_t(depth(a));
    if (!seek(doc, ap, error)) return false;
    UndoStack& s = doc.undo;
    // The current continuation becomes an inactive branch (all of it is redo steps now).
    const size_t n = path_.size() - 1 - ap;
    for (size_t k = 0; k < n && k < s.redo_.size(); ++k)
        nodes_[path_[ap + 1 + k]].stored = std::make_unique<UndoRecord>(std::move(s.redo_[s.redo_.size() - 1 - k]));
    s.redo_.clear();
    path_.resize(ap + 1);
    for (uint32_t c : chain) {
        nodes_[path_.back()].activeChild = c;
        path_.push_back(c);
    }
    for (uint32_t x = nodes_[id].activeChild; x != kNone && nodes_[x].alive; x = nodes_[x].activeChild) path_.push_back(x);
    for (size_t k = path_.size() - 1; k > ap; --k) {
        Node& node = nodes_[path_[k]];
        if (!node.stored) { // (shouldn't happen) cut the branch here
            path_.resize(k);
            s.redo_.clear();
            for (size_t j = path_.size() - 1; j > ap; --j) {
                s.redo_.push_back(std::move(*nodes_[path_[j]].stored));
                nodes_[path_[j]].stored.reset();
            }
            break;
        }
        s.redo_.push_back(std::move(*node.stored));
        node.stored.reset();
    }
    ++s.revision_;
    const int d = depth(id);
    if (d < 0 || size_t(d) >= path_.size()) {
        if (error) *error = "That branch couldn't be restored";
        return false;
    }
    return seek(doc, size_t(d), error);
}

bool Timeline::canRetune(uint32_t id, std::string* why) const {
    auto no = [&](const std::string& w) {
        if (why) *why = w;
        return false;
    };
    if (id >= nodes_.size() || !nodes_[id].alive || nodes_[id].parent == kNone) return no("Pick a stroke");
    const Node& n = nodes_[id];
    if (!onPath(id)) return no("Select the stroke's branch first");
    if (n.kind != Kind::Stroke) return no("Only sculpt strokes can be re-tuned");
    if (!n.fast) return no("This stroke can't be re-tuned (it was made on a sculpt layer, or its history was trimmed)");
    std::vector<uint32_t> todo(n.children.begin(), n.children.end());
    while (!todo.empty()) {
        const uint32_t x = todo.back();
        todo.pop_back();
        const UndoRecord* r = recordOf(x);
        if (!r) continue;
        if (r->mesh || r->topology || r->subdiv || r->part || !r->layerOffsets.empty() || (!r->positions.empty() && r->layer != -1))
            return no("A later step (\"" + nodes_[x].label + "\") changes the mesh as a whole; re-tuning would undo it");
        for (uint32_t c : nodes_[x].children) todo.push_back(c);
    }
    return true;
}

bool Timeline::retune(Document& doc, uint32_t id, float strength, std::string* error) {
    if (doc.undo.listener.get() != this) {
        if (error) *error = "This timeline doesn't watch the document's history";
        return false;
    }
    sync(doc);
    if (!canRetune(id, error)) return false;
    strength = std::clamp(strength, 0.0f, 4.0f);
    Node& n = nodes_[id];
    const float old = n.strength;
    if (std::abs(strength - old) < 1e-6f) return true;
    UndoRecord* r = recordOf(id);
    const size_t pos = size_t(depth(id));
    const bool applied = pos <= cursor_; // the mesh shows this stroke
    std::vector<glm::vec3>& before = applied ? r->positions.values : n.other;
    std::vector<glm::vec3>& after = applied ? n.other : r->positions.values;
    const auto& idx = r->positions.indices;
    if (n.retuneDelta.empty()) { // first re-tune: the stroke's own delta at strength 1 (old is 1 then)
        n.retuneDelta.resize(idx.size());
        for (size_t i = 0; i < idx.size(); ++i) n.retuneDelta[i] = after[i] - before[i];
    }
    std::vector<glm::vec3> d(idx.size());
    for (size_t i = 0; i < idx.size(); ++i) d[i] = (strength - old) * n.retuneDelta[i];
    for (size_t i = 0; i < idx.size(); ++i) after[i] += d[i];
    // Where later steps overlap the stroke, their stored positions move with it (both sides).
    std::vector<std::pair<uint32_t, uint32_t>> sorted(idx.size());
    for (size_t i = 0; i < idx.size(); ++i) sorted[i] = {idx[i], uint32_t(i)};
    std::sort(sorted.begin(), sorted.end());
    auto lookup = [&](uint32_t v) -> int64_t {
        auto it = std::lower_bound(sorted.begin(), sorted.end(), std::make_pair(v, uint32_t(0)));
        return it != sorted.end() && it->first == v ? int64_t(it->second) : -1;
    };
    std::vector<uint32_t> todo(n.children.begin(), n.children.end());
    while (!todo.empty()) {
        const uint32_t x = todo.back();
        todo.pop_back();
        for (uint32_t c : nodes_[x].children) todo.push_back(c);
        UndoRecord* rx = recordOf(x);
        if (!rx || rx->positions.empty()) continue;
        Node& nx = nodes_[x];
        const auto& ix = rx->positions.indices;
        const bool hasOther = nx.fast && nx.other.size() == ix.size();
        poolFor(ix.size(), [&](size_t b, size_t e) {
            for (size_t i = b; i < e; ++i) {
                const int64_t k = lookup(ix[i]);
                if (k < 0) continue;
                rx->positions.values[i] += d[size_t(k)];
                if (hasOther) nx.other[i] += d[size_t(k)];
            }
        }, 1 << 14);
    }
    // Checkpoints at or after the stroke.
    for (auto& [cid, ck] : checkpoints_) {
        bool below = false;
        for (uint32_t p = cid; p != kNone; p = nodes_[p].parent)
            if (p == id) {
                below = true;
                break;
            }
        if (!below) continue;
        for (size_t i = 0; i < idx.size(); ++i)
            if (idx[i] < ck.size()) ck[idx[i]] += d[i];
    }
    if (applied) {
        Mesh& mesh = doc.mesh;
        for (size_t i = 0; i < idx.size(); ++i) mesh.positions[idx[i]] += d[i];
        mesh.updateNormals(idx);
        doc.bvh.refit(mesh, idx);
    }
    n.strength = strength;
    ++doc.undo.revision_;
    return true;
}

// ---------------------------------------------------------------------------------------------------------------
// Saving

namespace {

constexpr char kMagic[8] = {'S', 'F', 'H', 'I', 'S', 'T', '1', '\0'};
constexpr char kSidecarMagic[8] = {'S', 'F', 'H', 'I', 'S', 'T', 'S', '\0'};
constexpr uint32_t kVersion = 1;

struct Writer {
    std::vector<uint8_t>& out;
    template <class T>
    void pod(const T& v) {
        const auto* p = reinterpret_cast<const uint8_t*>(&v);
        out.insert(out.end(), p, p + sizeof(T));
    }
    template <class T>
    void vec(const std::vector<T>& v) {
        pod(uint64_t(v.size()));
        const auto* p = reinterpret_cast<const uint8_t*>(v.data());
        out.insert(out.end(), p, p + v.size() * sizeof(T));
    }
    void str(const std::string& s) {
        pod(uint32_t(s.size()));
        out.insert(out.end(), s.begin(), s.end());
    }
};

struct Reader {
    const uint8_t* p;
    const uint8_t* end;
    bool ok = true;
    template <class T>
    T pod() {
        T v{};
        if (size_t(end - p) < sizeof(T)) {
            ok = false;
            return v;
        }
        std::memcpy(&v, p, sizeof(T));
        p += sizeof(T);
        return v;
    }
    template <class T>
    void vec(std::vector<T>& v) {
        const uint64_t n = pod<uint64_t>();
        if (!ok || n > uint64_t(end - p) / sizeof(T)) {
            ok = false;
            return;
        }
        v.resize(size_t(n));
        if (n) std::memcpy(v.data(), p, size_t(n) * sizeof(T));
        p += n * sizeof(T);
    }
    std::string str() {
        const uint32_t n = pod<uint32_t>();
        if (!ok || n > uint64_t(end - p)) {
            ok = false;
            return {};
        }
        std::string s(reinterpret_cast<const char*>(p), n);
        p += n;
        return s;
    }
};

bool savable(const UndoRecord& r) {
    return !r.mesh && !r.subdiv && !r.topology && !r.part && !r.texture && !r.textureTiles && !r.paint && !r.uv &&
           r.layerOffsets.empty() && r.layer == -1 && r.paintLayer == -1 && r.paintAlpha.empty();
}

template <class T>
void writeChannel(Writer& w, const UndoChannel<T>& c) {
    w.vec(c.indices);
    w.vec(c.values);
}
template <class T>
bool readChannel(Reader& rd, UndoChannel<T>& c) {
    rd.vec(c.indices);
    rd.vec(c.values);
    return rd.ok && c.indices.size() == c.values.size();
}

template <class T>
bool channelInRange(const UndoChannel<T>& c, size_t n) {
    for (uint32_t i : c.indices)
        if (i >= n) return false;
    return true;
}

} // namespace

// A fingerprint of the mesh a history belongs to.
static uint64_t meshFingerprint(const Mesh& mesh) {
    const size_t n = mesh.vertexCount();
    const size_t blocks = (n + (1 << 16) - 1) >> 16;
    std::vector<uint64_t> part(blocks, 0);
    poolFor(n, [&](size_t b, size_t e) {
        uint64_t h = 1469598103934665603ull;
        const auto* p = reinterpret_cast<const uint32_t*>(&mesh.positions[b]);
        for (size_t i = 0; i < (e - b) * 3; ++i) h = (h ^ p[i]) * 1099511628211ull;
        part[b >> 16] = h;
    }, 1 << 16);
    uint64_t h = 1469598103934665603ull ^ n ^ (uint64_t(mesh.triangleCount()) << 32);
    for (uint64_t x : part) h = (h ^ x) * 1099511628211ull;
    return h;
}

bool Timeline::save(std::vector<uint8_t>& out, const Mesh& mesh, std::string* error) const {
    // Which nodes can go in: the path from the newest unsavable step at or before the cursor, up to the first
    // unsavable one after it, and the branches off it that are savable all the way.
    auto ok = [&](uint32_t id) {
        const UndoRecord* r = recordOf(id);
        return r && savable(*r);
    };
    size_t first = 0;
    for (size_t i = 1; i <= cursor_; ++i)
        if (!ok(path_[i])) first = i;
    size_t last = cursor_;
    while (last + 1 < path_.size() && ok(path_[last + 1])) ++last;
    std::vector<uint32_t> order; // parents before children
    std::map<uint32_t, uint32_t> local;
    for (size_t i = first; i <= last; ++i) {
        local[path_[i]] = uint32_t(order.size());
        order.push_back(path_[i]);
    }
    for (size_t i = first; i <= last; ++i) { // inactive branches
        std::vector<uint32_t> todo;
        for (uint32_t c : nodes_[path_[i]].children)
            if (!local.count(c)) todo.push_back(c);
        while (!todo.empty()) {
            const uint32_t x = todo.back();
            todo.pop_back();
            if (!nodes_[x].alive || !ok(x)) continue;
            local[x] = uint32_t(order.size());
            order.push_back(x);
            for (uint32_t c : nodes_[x].children) todo.push_back(c);
        }
    }
    if (order.size() < 2) {
        if (error) *error = "Nothing in the history can be saved";
        return false;
    }
    out.clear();
    Writer w{out};
    out.insert(out.end(), kMagic, kMagic + 8);
    w.pod(kVersion);
    w.pod(uint64_t(mesh.vertexCount()));
    w.pod(uint64_t(mesh.triangleCount()));
    w.pod(meshFingerprint(mesh));
    w.pod(uint32_t(order.size()));
    w.pod(uint32_t(cursor_ - first)); // the cursor's local index (path nodes come first, in order)
    w.pod(uint32_t(last - first + 1)); // how many of the first nodes are the active branch
    for (size_t k = 0; k < order.size(); ++k) {
        const Node& n = nodes_[order[k]];
        const uint32_t parent = k == 0 ? kNone : local.at(n.parent);
        const uint32_t active = n.activeChild != kNone && local.count(n.activeChild) ? local.at(n.activeChild) : kNone;
        w.pod(parent);
        w.pod(active);
        w.pod(uint8_t(k == 0 ? Kind::Start : n.kind));
        w.pod(n.time);
        w.pod(n.strength);
        w.pod(n.touched);
        w.pod(n.center);
        w.pod(n.radius);
        w.str(k == 0 ? std::string("Start") : n.label);
        if (k == 0) continue;
        const UndoRecord& r = *recordOf(order[k]);
        writeChannel(w, r.positions);
        writeChannel(w, r.mask);
        writeChannel(w, r.colors);
        writeChannel(w, r.hidden);
        writeChannel(w, r.facegroups);
        w.pod(uint8_t(n.fast));
        if (n.fast) w.vec(n.other);
        w.vec(n.retuneDelta);
    }
    return true;
}

bool Timeline::load(Document& doc, const std::vector<uint8_t>& in, std::string* error) {
    auto fail = [&](const std::string& e) {
        if (error) *error = e;
        return false;
    };
    if (in.size() < 8 || std::memcmp(in.data(), kMagic, 8) != 0) return fail("Not a SculptForge history");
    Reader rd{in.data() + 8, in.data() + in.size()};
    if (rd.pod<uint32_t>() != kVersion) return fail("This history was saved by a newer SculptForge");
    const Mesh& mesh = doc.mesh;
    const uint64_t verts = rd.pod<uint64_t>(), tris = rd.pod<uint64_t>(), print = rd.pod<uint64_t>();
    if (!rd.ok || verts != mesh.vertexCount() || tris != mesh.triangleCount() || print != meshFingerprint(mesh))
        return fail("The history belongs to a different version of this mesh");
    const uint32_t count = rd.pod<uint32_t>(), cursor = rd.pod<uint32_t>(), pathLen = rd.pod<uint32_t>();
    if (!rd.ok || count < 2 || pathLen < 1 || pathLen > count || cursor >= pathLen) return fail("The history file is damaged");
    auto t = std::make_shared<Timeline>();
    t->nodes_.resize(count);
    std::vector<std::unique_ptr<UndoRecord>> records(count);
    for (uint32_t k = 0; k < count; ++k) {
        Node& n = t->nodes_[k];
        n.parent = rd.pod<uint32_t>();
        n.activeChild = rd.pod<uint32_t>();
        n.kind = Kind(rd.pod<uint8_t>());
        n.time = rd.pod<double>();
        n.strength = rd.pod<float>();
        n.touched = rd.pod<uint32_t>();
        n.center = rd.pod<glm::vec3>();
        n.radius = rd.pod<float>();
        n.label = rd.str();
        if (!rd.ok || (k == 0) != (n.parent == kNone) || (k > 0 && n.parent >= k) ||
            (n.activeChild != kNone && n.activeChild >= count))
            return fail("The history file is damaged");
        if (k > 0) t->nodes_[n.parent].children.push_back(k);
        if (k == 0) continue;
        auto r = std::make_unique<UndoRecord>();
        r->label = n.label;
        bool good = readChannel(rd, r->positions) && readChannel(rd, r->mask) && readChannel(rd, r->colors) &&
                    readChannel(rd, r->hidden) && readChannel(rd, r->facegroups);
        n.fast = rd.pod<uint8_t>() != 0;
        if (n.fast) rd.vec(n.other);
        rd.vec(n.retuneDelta);
        good = good && rd.ok && channelInRange(r->positions, verts) && channelInRange(r->mask, verts) &&
               channelInRange(r->colors, verts) && channelInRange(r->hidden, tris) && channelInRange(r->facegroups, tris) &&
               (!n.fast || n.other.size() == r->positions.indices.size()) &&
               (n.retuneDelta.empty() || n.retuneDelta.size() == r->positions.indices.size());
        if (!good || r->empty()) return fail("The history file is damaged");
        records[k] = std::move(r);
    }
    // The active branch is nodes 0 .. pathLen - 1, each the parent of the next.
    for (uint32_t k = 1; k < pathLen; ++k)
        if (t->nodes_[k].parent != k - 1) return fail("The history file is damaged");
    UndoStack& s = doc.undo;
    s.listener.reset();
    s.undo_.clear();
    s.redo_.clear();
    t->path_.resize(pathLen);
    for (uint32_t k = 0; k < pathLen; ++k) t->path_[k] = k;
    t->cursor_ = cursor;
    for (uint32_t k = 1; k <= cursor; ++k) s.undo_.push_back(std::move(*records[k]));
    for (uint32_t k = pathLen - 1; k > cursor; --k) s.redo_.push_back(std::move(*records[k]));
    for (uint32_t k = pathLen; k < count; ++k) t->nodes_[k].stored = std::move(records[k]);
    t->stack_ = &s;
    s.listener = t;
    t->sync(doc);
    return true;
}

std::string historySidecarPath(const std::string& projectPath) {
    std::filesystem::path p(projectPath);
    p.replace_extension(".sfhist");
    return p.string();
}

bool saveHistorySidecar(Document& doc, const std::string& projectPath, std::string* error) {
    std::vector<uint8_t> file(kSidecarMagic, kSidecarMagic + 8);
    Writer w{file};
    uint32_t saved = 0;
    std::vector<uint8_t> blob;
    std::vector<uint8_t> body;
    Writer wb{body};
    for (int i = 0; i < doc.partCount(); ++i) {
        bool shared = false; // a linked copy: its history (the group's) is saved with the group's first Part
        for (int k = 0; k < i; ++k) shared |= doc.parts[size_t(k)].data == doc.parts[size_t(i)].data;
        if (shared) continue;
        UndoStack& stack = doc.partUndo(i);
        Timeline* t = Timeline::of(stack);
        if (!t) continue;
        t->bindStack(stack);
        if (!t->save(blob, doc.partMesh(i))) continue;
        wb.pod(uint32_t(i));
        wb.str(doc.parts[size_t(i)].name);
        wb.vec(blob);
        ++saved;
    }
    const std::string path = historySidecarPath(projectPath);
    std::error_code ec;
    if (saved == 0) {
        std::filesystem::remove(path, ec); // a history from before would no longer match
        return true;
    }
    w.pod(kVersion);
    w.pod(saved);
    file.insert(file.end(), body.begin(), body.end());
    const std::string tmp = path + ".tmp";
    {
        std::ofstream f(std::filesystem::path(tmp), std::ios::binary | std::ios::trunc);
        f.write(reinterpret_cast<const char*>(file.data()), std::streamsize(file.size()));
        if (!f) {
            if (error) *error = "Couldn't write " + tmp;
            return false;
        }
    }
    std::filesystem::rename(tmp, path, ec);
    if (ec) {
        if (error) *error = "Couldn't write " + path + ": " + ec.message();
        return false;
    }
    return true;
}

int loadHistorySidecar(Document& doc, const std::string& projectPath, std::string* error) {
    const std::string path = historySidecarPath(projectPath);
    std::ifstream f(std::filesystem::path(path), std::ios::binary);
    if (!f) return 0;
    std::vector<uint8_t> file((std::istreambuf_iterator<char>(f)), std::istreambuf_iterator<char>());
    if (file.size() < 16 || std::memcmp(file.data(), kSidecarMagic, 8) != 0) {
        if (error) *error = path + " is not a SculptForge history";
        return 0;
    }
    Reader rd{file.data() + 8, file.data() + file.size()};
    if (rd.pod<uint32_t>() != kVersion) {
        if (error) *error = path + " was saved by a newer SculptForge";
        return 0;
    }
    const uint32_t count = rd.pod<uint32_t>();
    int loaded = 0;
    const int active = doc.activePart;
    for (uint32_t k = 0; k < count && rd.ok; ++k) {
        const uint32_t index = rd.pod<uint32_t>();
        const std::string name = rd.str();
        std::vector<uint8_t> blob;
        rd.vec(blob);
        if (!rd.ok || int(index) >= doc.partCount() || doc.parts[index].name != name) continue;
        doc.selectPart(int(index));
        std::string e;
        if (Timeline::load(doc, blob, &e)) ++loaded;
        else if (error) *error = e;
    }
    doc.selectPart(active);
    return loaded;
}

// ---------------------------------------------------------------------------------------------------------------
// Commands

namespace {

Timeline& ensureTimeline(Document& doc) {
    if (Timeline* t = Timeline::of(doc.undo)) {
        t->sync(doc);
        return *t;
    }
    return *Timeline::attach(doc);
}

const char* kindName(Timeline::Kind k) {
    switch (k) {
    case Timeline::Kind::Start: return "start";
    case Timeline::Kind::Stroke: return "stroke";
    case Timeline::Kind::Mask: return "mask";
    case Timeline::Kind::Paint: return "paint";
    case Timeline::Kind::Visibility: return "visibility";
    case Timeline::Kind::Topology: return "topology";
    default: return "other";
    }
}

} // namespace

void registerTimelineCommands(CommandRegistry& registry) {
    registry.add({"timeline_info", "Describe the Sculpt Timeline: steps on the active branch, the cursor, branches and checkpoints.",
                  {{"list", ParamSpec::Type::Bool, "List every step of the active branch", false}},
                  [](Document& doc, const Args& args) -> CommandResult {
                      Timeline& t = ensureTimeline(doc);
                      std::ostringstream s;
                      s << "Timeline: " << t.path().size() - 1 << " steps on the active branch, at step " << t.cursor()
                        << ", " << t.branches().size() << " other branches, " << t.checkpointCount() << " checkpoints ("
                        << t.checkpointBytes() / (1024 * 1024) << " MiB), history extras "
                        << t.extraBytes() / (1024 * 1024) << " MiB";
                      if (argBool(args, "list", false)) {
                          for (size_t i = 0; i < t.path().size(); ++i) {
                              const Timeline::Node& n = t.node(t.path()[i]);
                              s << "\n" << (i == t.cursor() ? "> " : "  ") << i << " #" << t.path()[i] << " " << kindName(n.kind)
                                << " \"" << n.label << "\" " << n.touched << (n.fast ? " fast" : "")
                                << (t.hasCheckpoint(t.path()[i]) ? " checkpoint" : "");
                              if (n.strength != 1.0f) s << " strength " << n.strength;
                          }
                          for (const Timeline::Branch& b : t.branches())
                              s << "\n  branch from step " << b.from << ": #" << b.first << " .. #" << b.tip << " (" << b.length << " steps)";
                      }
                      return {true, s.str()};
                  }});
    registry.add({"timeline_seek", "Show the model as it was after step `index` of the active branch (0 = the start).",
                  {{"index", ParamSpec::Type::Number, "Step on the active branch", true}},
                  [](Document& doc, const Args& args) -> CommandResult {
                      Timeline& t = ensureTimeline(doc);
                      const double v = argNumber(args, "index", -1.0);
                      if (v < 0) return {false, "index must be 0 or more"};
                      std::string e;
                      if (!t.seek(doc, size_t(v), &e)) return {false, e};
                      const auto& st = t.lastSeek();
                      std::ostringstream s;
                      s << "At step " << t.cursor() << " (" << st.ms << " ms; " << st.batched << " batched, " << st.walked
                        << " walked, " << st.replayed << " replayed" << (st.usedCheckpoint ? ", from a checkpoint" : "") << ")";
                      return {true, s.str()};
                  }});
    registry.add({"timeline_select", "Make the branch through step `node` (an id from timeline_info list) active and show it.",
                  {{"node", ParamSpec::Type::Number, "Step id (#)", true}},
                  [](Document& doc, const Args& args) -> CommandResult {
                      Timeline& t = ensureTimeline(doc);
                      std::string e;
                      if (!t.select(doc, uint32_t(argNumber(args, "node", -1.0)), &e)) return {false, e};
                      return {true, "At step " + std::to_string(t.cursor()) + " of the selected branch"};
                  }});
    registry.add({"timeline_retune", "Change how strongly a past stroke shows (1 = as sculpted, 0 = gone) without redoing the strokes after it.",
                  {{"node", ParamSpec::Type::Number, "Step id (#) of the stroke", true},
                   {"strength", ParamSpec::Type::Number, "0 .. 4", true}},
                  [](Document& doc, const Args& args) -> CommandResult {
                      Timeline& t = ensureTimeline(doc);
                      std::string e;
                      if (!t.retune(doc, uint32_t(argNumber(args, "node", -1.0)), float(argNumber(args, "strength", 1.0)), &e))
                          return {false, e};
                      doc.modified = true;
                      return {true, "Stroke re-tuned"};
                  }});
    registry.add({"timeline_save", "Save the history beside the project (<name>.sfhist).",
                  {{"path", ParamSpec::Type::String, "Project path (default: the open project)", false}},
                  [](Document& doc, const Args& args) -> CommandResult {
                      ensureTimeline(doc);
                      const std::string path = argString(args, "path", doc.path);
                      if (path.empty()) return {false, "Save the project first (or give a path)"};
                      std::string e;
                      if (!saveHistorySidecar(doc, path, &e)) return {false, e};
                      return {true, "History saved to " + historySidecarPath(path)};
                  }});
    registry.add({"timeline_load", "Load the history saved beside the project (<name>.sfhist), if it matches the mesh.",
                  {{"path", ParamSpec::Type::String, "Project path (default: the open project)", false}},
                  [](Document& doc, const Args& args) -> CommandResult {
                      const std::string path = argString(args, "path", doc.path);
                      if (path.empty()) return {false, "No project path"};
                      std::string e;
                      const int n = loadHistorySidecar(doc, path, &e);
                      if (n == 0) return {false, e.empty() ? "No history beside " + path : e};
                      return {true, "History loaded for " + std::to_string(n) + " Part(s)"};
                  }});
}

} // namespace sf