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.

22.7 KB
Raw Blame
// SculptForge - open source digital sculpting
// SPDX-License-Identifier: GPL-3.0-or-later
//
// Micro-displacement levels: hundreds of millions of sculptable triangles without a mesh that size.
//
// Above the top subdivision level a Part can carry a micro level (Mesh::micro). The surface is then
//
//     micro point = S(t, i, j) + d(t, i, j) * N(t, i, j)
//
// for every base triangle t (the mesh itself: its current, highest subdivision level) and every point (i, j) of
// a regular grid of n = 2^level segments per base edge on it (n^2 micro triangles per base triangle):
//  - S is the base triangle's Phong-tessellated surface (Boubekeur & Alexa 2008, shape factor 3/4): the flat
//    point pulled towards the tangent planes of the three corners, which is smooth across base edges and needs
//    nothing but the base positions and normals;
//  - N is the interpolated base vertex normal (normalised);
//  - d is ONE scalar per grid point, stored as a 16-bit integer times `step` (world units).
// Micro triangles are never stored: positions are generated on the fly (brushes on the CPU, the renderer in its
// vertex shader). Memory is 2 bytes per grid point (+1 with a mask): 300 million micro triangles at level 4 on
// 1.2 million base triangles are about 360 MB, against roughly 30 GB as a plain mesh.
//
// Each base triangle keeps its whole grid, so the points on a base edge exist once per triangle beside it (and a
// corner once per triangle around it): about 20% extra at level 4 for grids that are contiguous per triangle (a
// brush, an undo tile and a GPU upload are one memcpy-able run each). After every edit the copies are made equal
// again ("stitching"), so the surface stays watertight. Positions on shared edges are computed from the base
// corners in ascending vertex-index order on the CPU and GPU alike, so both sides of an edge get bit-identical
// points even where the compiler fuses multiply-adds.
//
// Grid layout per triangle (corners c0, c1, c2 = triangle.x, .y, .z): point (i, j) with i, j >= 0, i + j <= n
// has barycentric weights ((n - i - j) / n, i / n, j / n); row j holds n + 1 - j points, so its index is
// j * (n + 1) - j * (j - 1) / 2 + i. Corner c0 = (0, 0), c1 = (n, 0), c2 = (0, n). Edge e runs from corner e to
// corner e + 1: e0 = (k, 0), e1 = (n - k, k), e2 = (0, n - k), k = 0..n.
//
// What a scalar displacement can't do: move points sideways. Brushes that slide the surface (Move's sideways
// part, Snake Hook, Nudge, VDM stamps with overhangs) work on real subdivision levels; on a micro level Pinch
// resamples the heights from where its pull would bring the surface (see microBrushSupport).
#pragma once

#include "core/Mesh.h"
#include "core/MicroStore.h"

#include <cstdint>
#include <functional>
#include <memory>
#include <mutex>
#include <span>
#include <string>
#include <vector>

namespace sf {

class BVH;
class CommandRegistry;
class FocusDetail;
struct Document;
struct RayHit;
enum class BrushType;

struct MicroMesh {
    static constexpr int kMaxLevel = 7;       // 128 x 128 segments per base triangle (8,385 points)
    static constexpr float kPhong = 0.75f;    // Phong tessellation shape factor
    static constexpr uint32_t kNone = ~0u;

    int level = 0;            // n = 2^level segments per base edge
    uint32_t n = 1;
    uint32_t samples = 3;     // grid points per base triangle: (n + 1)(n + 2) / 2
    float step = 1e-6f;       // world units per integer unit of `disp`
    uint32_t baseTriangles = 0, baseVertices = 0;
    MicroStore disp;                // baseTriangles * samples (in memory or out of core: core/MicroStore.h)
    std::vector<uint8_t> mask;      // empty, or one per grid point (0 = free, 255 = masked)
    std::vector<uint16_t> triRange; // per base triangle: the largest |disp| (an upper bound; brushes find triangles with it)
    uint16_t rangeMax = 0;          // the largest triRange (an upper bound)
    float bulgeMax = 0.0f;          // the most S leaves a base triangle's plane (world units, an upper bound)
    float baseEdge = 0.0f;          // the base's average edge length

    // Base topology this level needs (derived, not saved; rebuilt when the base changes): per triangle edge the
    // neighbouring triangle (tri << 2 | its edge), or kNone on a boundary.
    std::vector<uint32_t> edgeNeighbor;

    // Picks and brushes find the base triangles a displaced surface may reach through the BVH, each node grown by the
    // largest displacement under it (not the level's largest everywhere: one tall stroke made every query on a
    // dense base visit millions of triangles). Derived, per BVH: microQueryTriangles / microRayTriangles keep it.
    struct Reach {
        std::mutex lock;
        const void* bvh = nullptr;
        uint64_t structure = 0;
        float step = 0.0f;
        std::vector<float> pad;     // per BVH node, world units (upper bounds: they only shrink on a full pass)
        std::vector<uint64_t> bits; // base triangles changed since (markDirty)
        bool all = true;            // everything (markAllDirty, a rescale, a new level)
        Reach() = default;
        Reach(const Reach&) {} // (a copy starts over: it may be checked against another BVH)
        Reach& operator=(const Reach&) {
            all = true, bvh = nullptr;
            return *this;
        }
    };
    mutable Reach reach;

    // What changed since the renderer last looked: per base triangle a bit, or everything.
    std::vector<uint64_t> dirtyBits;
    bool allDirty = true;
    bool maskDirty = false; // the mask was added or removed (the renderer's shading changes everywhere)
    bool stroking = false;  // a stroke is running (TierConfig draft normals: the renderer shades less meanwhile)
    bool rescaled = false;  // `step` grew and every value was rescaled (same surface: the renderer re-sends the values only)
    uint64_t revision = 0;  // bumped by every edit
    // Which level this is (new on Divide / load; kept by copies, which hold the same values): the renderer keeps
    // its GPU copy while the serial stays.
    uint64_t serial = 0;
    static uint64_t newSerial();
    // Focus Detail (core/FocusDetail.h, prototype): set when the level streams from a detail file. Tiles outside
    // the focus hold a coarse grid; brushes and undo make the tiles they change full first (ensureFull).
    std::shared_ptr<FocusDetail> focus;

    size_t microTriangles() const { return size_t(baseTriangles) * n * n; }
    size_t microVertices() const; // unique grid points (shared edges and corners counted once)
    size_t bytes() const;
    bool hasMask() const { return !mask.empty(); }
    float rangeWorld() const { return 32767.0f * step; } // the largest |d| `step` can hold

    static uint32_t index(uint32_t i, uint32_t j, uint32_t n) { return j * (n + 1) - j * (j - 1) / 2 + i; }
    // The grid point of edge e at k (from corner e towards corner e + 1).
    static void edgePoint(int e, uint32_t k, uint32_t n, uint32_t& i, uint32_t& j) {
        if (e == 0) i = k, j = 0;
        else if (e == 1) i = n - k, j = k;
        else i = 0, j = n - k;
    }
    void markDirty(uint32_t tri) {
        dirtyBits[tri >> 6] |= uint64_t(1) << (tri & 63);
        if (!reach.bits.empty()) reach.bits[tri >> 6] |= uint64_t(1) << (tri & 63);
    }
    // Grows `step` (by powers of two, at least 4x) until +/-`need` world units fit, rescaling every value (each
    // loses its lowest bits). Returns the divisor applied (1 = it fitted already).
    int widen(float need);
    void markAllDirty() { allDirty = true, reach.all = true; }
    void clearDirty();
    // Builds edgeNeighbor for `base` (if it doesn't fit already).
    void ensureTopology(const Mesh& base);
};

// --- The two-tier engine's vocabulary ---
// BaseCage: the coarse surface the brushes for big forms (Move, transforms) deform: the Part's mesh, its highest
// subdivision level. Its polygons are triangles (a quad of the cage is a triangle pair, one patch each).
using BaseCage = Mesh;
// MicroPatch: one base triangle's regular grid of scalar heights (n + 1)(n + 2) / 2, implicit topology (no index
// buffer anywhere), heights 16-bit in memory and packed to their range (0-16 bits) on disk and in undo steps.
struct MicroPatch {
    uint32_t id = 0;   // the base triangle
    uint32_t n = 0;    // segments per edge
    int16_t* heights = nullptr;
    uint8_t* mask = nullptr; // null without a mask
    size_t points() const { return size_t(n + 1) * (n + 2) / 2; }
};
MicroPatch microPatch(Mesh& m, uint32_t id);
// PatchPageTable: which patches are resident. In memory every patch is; out of core (MicroStore::mapped) a patch
// is resident when its pages are, cold ones live in the sparse file (untouched = a hole) and come back on touch;
// the operating system's page cache keeps the LRU order and trim() enforces TierConfig::residentCacheCapMB.
class PatchPageTable {
public:
    explicit PatchPageTable(MicroMesh& mm) : mm_(mm) {}
    bool resident(uint32_t patch) const;
    size_t residentPatches() const;
    size_t residentBytes() const { return mm_.disp.residentBytes(); }
    size_t trim(size_t maxBytes) { return mm_.disp.trim(maxBytes); }

private:
    MicroMesh& mm_;
};

// The base triangle's corners and normals, sorted by vertex index, for evaluating its grid points.
struct MicroTriangle {
    glm::vec3 p[3], nrm[3]; // in vertex-index order
    uint8_t slot[3];        // which corner (0..2 of the triangle) each is
    float invN = 1.0f;
    uint32_t n = 1;
    void set(const Mesh& base, uint32_t tri, uint32_t n);
    // The reference surface S and direction N at grid point (i, j).
    void eval(uint32_t i, uint32_t j, glm::vec3& surface, glm::vec3& normal) const;
    // ... and at barycentric weights of corners 0..2 (sum 1).
    void evalWeights(const float w[3], glm::vec3& surface, glm::vec3& normal) const;
    // The flat point (no Phong) at grid point (i, j): what displacement maps are measured from.
    glm::vec3 flat(uint32_t i, uint32_t j) const;
};

// --- Queries ---
inline bool hasMicro(const Mesh& m) { return m.micro != nullptr; }
int microLevel(const Mesh& m); // 0 = none
size_t microTriangleCount(const Mesh& m);
size_t microBytes(const Mesh& m);
// "Micro 4 (300.0M)" or "".
std::string microText(const Mesh& m);
// True when the micro level still fits the mesh (base triangle and vertex counts).
bool microMatches(const Mesh& m);
// The micro level to change in place: copied first when another Mesh (an undo snapshot, a copy) shares it.
MicroMesh& mutableMicro(Mesh& m);
// The most micro triangles this computer is allowed to make (RAM: about 4 bytes a grid point with the GPU's share).
size_t microMaxTriangles();
// The level that brings the mesh closest to `targetTriangles` micro triangles (1..kMaxLevel).
int microLevelFor(const Mesh& m, size_t targetTriangles);

// The micro surface point at grid point (i, j) of base triangle t (reads the stored displacement).
glm::vec3 microPoint(const Mesh& m, uint32_t tri, uint32_t i, uint32_t j);
// The micro surface at barycentric weights of base triangle t (displacement interpolated on the micro triangle
// holding the point), with its geometric normal.
glm::vec3 microPointAt(const Mesh& m, uint32_t tri, const float w[3], glm::vec3* normal = nullptr);

// --- Operations (no undo; see the commands) ---
// Adds a micro level of `level` (1..kMaxLevel) to the mesh: its current level must be the highest (or it has no
// subdivision levels). The surface starts as S (smooth, d = 0).
// `outOfCore`: 1 = keep the displacements in a memory-mapped file (core/MicroStore.h), 0 = in memory, -1 = decide
// (out of core when they'd take more than a quarter of this computer's memory, or SF_MICRO_OUT_OF_CORE=1).
bool microDivide(Mesh& m, int level, std::string& error, int outOfCore = -1);
// The -1 rule of microDivide for `points` grid points.
bool microWantsOutOfCore(size_t points);
// Removes the micro level.
void microDelete(Mesh& m);
// Gives a loaded mesh (with normals) a micro level from saved data: `disp` holds baseTriangles * samples values
// (`mask` that many or none). Works out the derived data (ranges, bulge, edge neighbours).
bool microAttach(Mesh& m, int level, float step, MicroStore disp, std::vector<uint8_t> mask, std::string& error);
// A regular mesh of the micro surface at micro level `level` (<= the micro level): shared points welded, the base
// triangles' UVs, face groups and hidden flags carried to their micro triangles, mask from the micro mask. Fails
// when it would exceed `maxTriangles` (0 = what subdivision Divide allows on this computer).
bool microBakeMesh(const Mesh& m, int level, Mesh& out, std::string& error, size_t maxTriangles = 0);
// Displacement maps over the base UVs (needs UVs): `vector` = object-space offset of the micro surface from the
// flat base triangles (RGB), else the height along the interpolated normal from the flat base triangles.
// `format` "exr" (32-bit float, world units) or "png" (16-bit; scalar: 32768 = 0 and +/-`scaleOut` at white /
// black; vector: each channel likewise). Writes `path`.
bool microExportDisplacement(const Mesh& m, const std::string& path, int size, bool vector, const std::string& format,
                             float& scaleOut, std::string& error);
// Adds procedural detail (value noise of `frequency` cycles per unit, `amplitude` world units) over the whole
// micro surface, for demos and benchmarks.
void microNoise(Mesh& m, float amplitude, float frequency, uint32_t seed = 1);

// Ray against the micro surface: the base triangle hit (BVH) and its neighbourhood within the displacement range,
// at full micro resolution. hit.triangle is the base triangle; hit.position / normal are on the micro surface.
bool microRaycast(const Mesh& m, const BVH& bvh, const glm::vec3& origin, const glm::vec3& dir, RayHit& hit);
// After the base moved under a micro level (brushes on the base: Sculptor::microBaseDab, Move): its bulge bound
// raised to what the base's triangles now need.
void microRaiseBulge(Mesh& m);
// The base triangles whose displaced surface may come within `radius` of `center` (each BVH node grown by the
// largest displacement and bulge under it, MicroMesh::Reach), for the caller's exact test per triangle.
void microQueryTriangles(const Mesh& m, const BVH& bvh, const glm::vec3& center, float radius, std::vector<uint32_t>& out);
// ... and those whose displaced surface the ray may cross.
void microRayTriangles(const Mesh& m, const BVH& bvh, const glm::vec3& origin, const glm::vec3& dir, std::vector<uint32_t>& out);
// bvh.raycast, or microRaycast on a mesh with a micro level: what brushes and the cursor pick.
bool surfaceRaycast(const Mesh& m, const BVH& bvh, const glm::vec3& origin, const glm::vec3& dir, RayHit& hit);

// --- Shading for the renderer: per grid point an octahedral normal (2 x 8 bits), curvature (8 bits,
// sign(c) sqrt|c| like the mesh shader's) and mask (8 bits), packed little-endian in a uint32. ---
class MicroShader {
public:
    // Recomputes what changes when base triangles `dirty` changed (all of them when `all`): the shading of those
    // and of every base triangle sharing a vertex with one (whose shared edges and corners average with them).
    // out(tri) gives where that triangle's `samples` values go (each written whole). `written` lists them.
    // `prepare`, if given, sees the triangles about to be written (before any out() call), once per batch.
    // `grow` false: the dirty triangles alone are written (exact: their neighbours' edge sums are read, not written);
    // the neighbours whose shared points changed (those sharing a vertex) go to `outer`, to write later.
    using Prepare = std::function<void(std::span<const uint32_t> tris)>;
    void 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 = true,
               std::vector<uint32_t>* outer = nullptr);

private:
    // shade() for the triangles `seeds` (grown by the triangles sharing a vertex when `grow`); appends to `written`.
    void shadeSet(const Mesh& m, std::span<const uint32_t> seeds, bool grow, std::vector<uint32_t>& written,
                  const std::function<uint32_t*(uint32_t tri)>& out, const Prepare& prepare, std::vector<uint32_t>* outer = nullptr);
    std::vector<uint32_t> seed_, grown_;
    std::vector<uint32_t> stamp_, slot_; // per base triangle: in a set of this call (stamp), its partials (slot)
    std::vector<uint32_t> vstamp_;       // per base vertex
    uint32_t epoch_ = 0;
    std::vector<uint32_t> ring_, ring2_;
    std::vector<float> partial_;         // per slot: 3n edge points x 6 floats
};

// --- Brushes (driven by Sculptor, which calls these when the mesh has a micro level) ---

// Whether a brush works on micro levels: 2 = as on a mesh, 1 = approximated (Pinch, Crease and Sharp Crease
// resample the heights from where their pull would bring the surface; Move moves along the normal), 0 = not at all.
int microBrushSupport(BrushType type);

struct BrushAlpha;
struct MicroUndo;
class MicroStroke {
public:
    void begin(Mesh& m);
    // One dab (one mirror) of a displacement brush, or the mask brush (`maskBrush`: raises the mask to 1, or
    // lowers it with invert). `alpha` (null/empty = round) shapes a displacement dab as on a mesh, its top edge
    // toward `alphaUp` (#92).
    void dab(Mesh& m, const BVH& bvh, BrushType type, const glm::vec3& center, const glm::vec3& viewDir, float radius,
             float strength, bool invert, float focal, const glm::vec3& alphaUp, bool maskBrush, float maskStrength,
             const BrushAlpha* alpha = nullptr, const std::function<float(const glm::vec3&)>& texture = {},
             const glm::vec3& strokeDir = glm::vec3(0.0f));
    // (texture: a brush recipe's surface pattern, 0..1 at a surface point, times the tip; #120. strokeDir: where the
    // stroke is heading, for Sharp Crease's pull across it; 0 = none)
    // Move: captures the points within the dab (with each mirror's signs), then moves them along their normals.
    void beginGrab(Mesh& m, const BVH& bvh, const glm::vec3& center, float radius, float focal, const glm::mat3& mirror);
    void grab(Mesh& m, const glm::vec3& delta);
    // Puts every grid point the stroke changed back (the stroke stays open).
    void restore(Mesh& m);
    // The stroke's undo step (null when nothing changed).
    std::unique_ptr<MicroUndo> end(Mesh& m);
    bool active() const { return active_; }
    // Scale-adaptive brushing: a dab is evaluated on grid points about radius / kBrushSamples apart (a power-of-two
    // stride of the micro grid) and interpolated in between, so its evaluation cost doesn't grow with the micro
    // level. Off: every grid point (tests compare).
    static constexpr int kBrushSamples = 48;
    bool adaptive = true;
    uint32_t lastStride = 1; // the stride the last dab used
    // Timings of the last dabs (ms): finding the triangles + saving undo tiles, the kernel, stitching.
    double findMs = 0, kernelMs = 0, stitchMs = 0;
    uint64_t points = 0; // grid points visited

private:
    std::vector<uint8_t> changed_;        // per candidate of the last dab: the kernel changed its grid
    std::vector<int16_t> snap_;           // Pinch, Crease, Sharp Crease: the grids of this dab's triangles as it found them
    std::vector<uint32_t> snapOf_;        // per base triangle: its grid in snap_ + 1 (0 = none)
    std::vector<uint32_t> stitchStamp_;   // per base triangle: dabEpoch_ when the stitch changed a point of it
    void touch(MicroMesh& mm, std::span<const uint32_t> tris);
    void widen(MicroMesh& mm, float need); // MicroMesh::widen, keeping this stroke's saved tiles in step
    // `changed` (per entry of tris, or null: all): the triangles the kernel wrote; only they and those the stitch
    // changed are marked dirty (the renderer re-sends, re-bounds and re-shades what's marked).
    void stitch(const Mesh& m, MicroMesh& mm, std::span<const uint32_t> tris, const uint8_t* changed = nullptr);
    bool active_ = false;
    float strokeStep_ = 0.0f;
    std::vector<uint32_t> tileOf_;        // per base triangle: its undo tile + 1 (0 = not yet touched)
    std::vector<uint32_t> tiles_;         // the touched base triangles, in order
    std::vector<int16_t> oldDisp_;        // tiles_.size() * samples
    std::vector<uint8_t> oldMask_;        // likewise, while the mask exists
    bool maskAdded_ = false;              // the stroke allocated the mask
    std::vector<uint32_t> cand_;          // this dab's base triangles
    std::vector<uint32_t> dabStamp_;      // per base triangle: == dabEpoch_ when in cand_
    uint32_t dabEpoch_ = 0;
    std::vector<uint32_t> vertStamp_;
    std::vector<uint32_t> corners_;
    float baseEdge_ = 0.0f; // the base's average edge length
    // Move: per mirror its triangles and, per triangle, weight and direction of its coarse grid points.
    struct GrabMirror {
        glm::mat3 mirror{1.0f};
        uint32_t stride = 1, firstTri = 0, tris = 0;
    };
    std::vector<GrabMirror> grabMirrors_;
    std::vector<uint32_t> grabTris_;
    std::vector<float> grabWeight_;
    std::vector<glm::vec3> grabNormal_;
};

// One micro step: the old grid points of the base triangles a stroke touched (in units of `step`), or a whole
// micro level swapped in or out (Divide to micro, Delete micro: `whole`, with `swapWhole`).
//
// Strokes keep a journal (`journal`): the touched tiles sorted by a Morton code of their centre (`keys`, so the
// journal of a region is contiguous and can be looked up), each as the stroke's change (new - old, stored as the
// difference to the point before it in its row, or below it for a row's first) packed with the tile codec (core/MicroStore.h): untouched points cost nothing, a smooth change a few bits
// per point, so a typical stroke's step is tens of KB instead of 2 bytes per point. `applied`: the change is in
// the mesh (undo subtracts it, redo adds it back).
struct MicroUndo {
    float step = 0.0f;
    uint32_t samples = 0;
    std::vector<uint32_t> tris;
    std::vector<int16_t> disp;       // whole-tile old values (no journal)
    bool journal = false;
    bool applied = true;
    std::vector<uint64_t> keys;      // journal: Morton code of each tile's centre, ascending
    std::vector<uint8_t> packed;     // journal: the tiles' changes (each point less its predecessor), packed
    std::vector<int16_t> firsts;     // journal: each tile's first change
    std::vector<uint8_t> mask;
    bool maskAdded = false; // the step allocated the mask: undo frees it again (redo brings it back)
    bool swapWhole = false;
    std::shared_ptr<MicroMesh> whole;
    void swapWith(Mesh& m);
    size_t bytes() const;
};

// --- Undoable document operations ---
bool microDivideUndoable(Document& doc, int level, std::string& message);
bool microDeleteUndoable(Document& doc, std::string& message);

// micro_divide, micro_delete, micro_info, micro_bake, micro_export_displacement, micro_noise.
void registerMicroCommands(CommandRegistry& registry);

} // namespace sf