Free, open-source 3D sculpting for Linux, macOS and Windows: dense meshes, remeshing, painting, built-in AI (image/text to 3D), Send to Unreal, game-ready LODs, Gaussian splats and OpenUSD.
C++ 3d3d-sculptingcppdear-imguidigital-sculptingfbxgame-developmentgaussian-splattinggltfimage-to-3dmcpopenglopenusdsculptingtext-to-3dunreal-engine
// SculptForge - open source digital sculpting
// SPDX-License-Identifier: GPL-3.0-or-later
//
// Brushes on micro-displacement levels (core/Micro.h). A dab:
// 1. finds the base triangles it can reach: the BVH over the base, with the radius grown by how far the micro
// surface can leave the base (the Phong bulge plus the largest displacement), then each triangle's own box;
// 2. saves the grids of triangles the stroke touches for the first time (the undo step: whole tiles);
// 3. finds the brush plane (area normal and centre) from every second grid point under the brush;
// 4. runs the kernel over the triangles in parallel: each grid point inside the brush gets a new scalar;
// 5. stitches: copies of a point on a shared edge or corner are averaged (they differ only where a brush read
// neighbours, like Smooth), so the surface stays closed.
#include "core/Micro.h"
#include "core/FocusDetail.h"
#include "core/BVH.h"
#include "core/BrushAlpha.h"
#include "core/Sculpt.h"
#include "core/ThreadPool.h"
#include "core/TierConfig.h"
#include <algorithm>
#include <atomic>
#include <cmath>
namespace sf {
int microBrushSupport(BrushType type) {
switch (type) {
case BrushType::Standard:
case BrushType::Clay:
case BrushType::ClayBlock:
case BrushType::Smooth:
case BrushType::Inflate:
case BrushType::Flatten:
case BrushType::Trim:
case BrushType::Layer: return 2;
case BrushType::Pinch:
case BrushType::Crease:
case BrushType::SharpCrease:
case BrushType::Move: return 1;
default: return 0;
}
}
namespace {
glm::vec3 projectOnPlane(const glm::vec3& v, const glm::vec3& n) { return v - n * glm::dot(v, n); }
// A base triangle's box grown by its Phong bulge and displacement range.
bool triangleNear(const Mesh& m, const MicroMesh& mm, uint32_t t, const glm::vec3& c, float r) {
const glm::uvec3 tr = m.triangles[t];
const glm::vec3 a = m.positions[tr.x], b = m.positions[tr.y], d = m.positions[tr.z];
const glm::vec3 na = m.normals[tr.x], nb = m.normals[tr.y], nd = m.normals[tr.z];
float bulge = 0.0f;
bulge = std::max({bulge, std::abs(glm::dot(b - a, na)), std::abs(glm::dot(d - a, na)), std::abs(glm::dot(a - b, nb)),
std::abs(glm::dot(d - b, nb)), std::abs(glm::dot(a - d, nd)), std::abs(glm::dot(b - d, nd))});
const float grow = bulge * MicroMesh::kPhong + float(mm.triRange[t]) * mm.step;
const glm::vec3 lo = glm::min(a, glm::min(b, d)) - grow, hi = glm::max(a, glm::max(b, d)) + grow;
const glm::vec3 q = glm::clamp(c, lo, hi);
return glm::dot(q - c, q - c) <= r * r;
}
// Every grid point of an n-grid with the values on the points `stride` apart (a grid of n / stride) interpolated
// over the coarse micro triangle holding it (exactly the coarse value on coarse points): each(index, i, j, value).
template <class T, class F>
void forInterpolated(const T* coarse, uint32_t n, uint32_t stride, F&& each) {
const uint32_t cm = n / stride;
const float inv = 1.0f / float(stride);
uint32_t idx = 0;
for (uint32_t j = 0; j <= n; ++j) {
const uint32_t cj = j / stride, rj = j % stride;
const float fj = float(rj) * inv;
for (uint32_t i = 0; i + j <= n; ++i, ++idx) {
const uint32_t ci = i / stride, ri = i % stride;
const float fi = float(ri) * inv;
T d;
if (ri == 0 && rj == 0) d = coarse[MicroMesh::index(ci, cj, cm)];
else if (fi + fj <= 1.0f)
d = coarse[MicroMesh::index(ci, cj, cm)] * (1.0f - fi - fj) + coarse[MicroMesh::index(ci + 1, cj, cm)] * fi +
coarse[MicroMesh::index(ci, cj + 1, cm)] * fj;
else
d = coarse[MicroMesh::index(ci + 1, cj, cm)] * (1.0f - fj) + coarse[MicroMesh::index(ci + 1, cj + 1, cm)] * (fi + fj - 1.0f) +
coarse[MicroMesh::index(ci, cj + 1, cm)] * (1.0f - fi);
each(idx, i, j, d);
}
}
}
// Writes the change at every grid point from `coarse` changes on the points `stride` apart (forInterpolated):
// apply(index, change) for the points whose change isn't 0.
template <class F>
void interpolateCoarse(const float* coarse, uint32_t n, uint32_t stride, F&& apply) {
forInterpolated(coarse, n, stride, [&](uint32_t idx, uint32_t, uint32_t, float d) {
if (d != 0.0f) apply(idx, d);
});
}
// Rounds `units` (a displacement over its step) to the nearest storable value (no libm call: brushes write
// millions of these).
inline int16_t quantizeUnits(float units) {
units = std::clamp(units, -32767.0f, 32767.0f);
return int16_t(units >= 0.0f ? int(units + 0.5f) : -int(0.5f - units));
}
// The six lattice neighbours of (i, j) inside the triangle.
template <class F>
void forNeighbors(uint32_t i, uint32_t j, uint32_t n, F&& f) {
if (i > 0) f(i - 1, j);
if (i + j < n) f(i + 1, j);
if (j > 0) f(i, j - 1);
if (i + j < n) f(i, j + 1);
if (j > 0) f(i + 1, j - 1);
if (i > 0) f(i - 1, j + 1);
}
// Pinch on a height field (Pinch, Crease, Sharp Crease; #125). Pulling the surface sideways towards the brush
// centre is, for a scalar displacement, resampling it from farther out: each point takes the value found where the
// pull brings the surface from (semi-Lagrangian). The values come from the grids as the dab found them (`snap` for
// the triangles it writes), interpolated on the micro triangles, walking across base triangles as far as the pull
// reaches. A scale-adaptive dab (stride > 1) works out the pull on its coarse points and resamples every grid point
// with it interpolated: resampling only the coarse points and interpolating their change handed each coarse point's
// detail to the points between, dab after dab (a hatch along big strokes). An interpolated value never leaves the range of the values around it, so
// unlike sharpening against the neighbours' average (which made every dab grow grid-scale noise) nothing amplifies,
// however many dabs land on a point.
struct PinchSampler {
const Mesh& m;
const MicroMesh& mm;
const int16_t* snap = nullptr;
const uint32_t* snapOf = nullptr; // per base triangle: its tile in `snap` + 1 (0: not written this dab, read mm.disp)
const int16_t* grid(uint32_t t) const {
return snapOf[t] ? snap + size_t(snapOf[t] - 1) * mm.samples : mm.disp.data() + size_t(t) * mm.samples;
}
// The flat base point of grid point (i, j) of triangle t (corners in triangle order).
glm::vec3 flat(uint32_t t, float i, float j) const {
const glm::uvec3 tr = m.triangles[t];
const glm::vec3 a = m.positions[tr.x];
const float inv = 1.0f / float(mm.n);
return a + (m.positions[tr.y] - a) * (i * inv) + (m.positions[tr.z] - a) * (j * inv);
}
// The displacement (in units of the step) at `q` near the flat base, starting from triangle t.
float sample(uint32_t t, const glm::vec3& q) const {
float w1 = 0.0f, w2 = 0.0f;
for (int steps = 0;; ++steps) {
const glm::uvec3 tr = m.triangles[t];
const glm::vec3 a = m.positions[tr.x], e1 = m.positions[tr.y] - a, e2 = m.positions[tr.z] - a, d = q - a;
const float g11 = glm::dot(e1, e1), g12 = glm::dot(e1, e2), g22 = glm::dot(e2, e2);
const float det = g11 * g22 - g12 * g12;
if (!(det > 0.0f)) break; // (degenerate: its first corner)
const float d1 = glm::dot(d, e1), d2 = glm::dot(d, e2);
w1 = (g22 * d1 - g12 * d2) / det;
w2 = (g11 * d2 - g12 * d1) / det;
const float w0 = 1.0f - w1 - w2;
// Outside: on to the neighbour across the edge facing the most negative weight (edge e runs from corner
// e to e + 1, so w2 < 0 is past edge 0, w0 past edge 1, w1 past edge 2).
const float lowest = std::min({w0, w1, w2});
if (lowest >= -1e-5f || steps == 32) break;
const int e = lowest == w2 ? 0 : lowest == w0 ? 1 : 2;
const uint32_t nb = mm.edgeNeighbor[size_t(t) * 3 + size_t(e)];
if (nb == MicroMesh::kNone) break; // (a boundary: the nearest point inside)
t = nb >> 2;
}
// Clamped into the triangle.
w1 = std::max(w1, 0.0f), w2 = std::max(w2, 0.0f);
if (w1 + w2 > 1.0f) {
const float k = 1.0f / (w1 + w2);
w1 *= k, w2 *= k;
}
const uint32_t cm = mm.n, n = mm.n;
const int16_t* g = grid(t);
const float fi = w1 * float(cm), fj = w2 * float(cm);
uint32_t i0 = std::min(uint32_t(fi), cm - 1), j0 = std::min(uint32_t(fj), cm - 1);
if (i0 + j0 > cm - 1) {
if (fi >= fj) i0 = cm - 1 - j0;
else j0 = cm - 1 - i0;
}
const float a = std::clamp(fi - float(i0), 0.0f, 1.0f), b = std::clamp(fj - float(j0), 0.0f, 1.0f);
auto at = [&](uint32_t i, uint32_t j) { return float(g[MicroMesh::index(i, j, n)]); };
if (a + b <= 1.0f || i0 + j0 + 2 > cm) {
const float c = std::max(1.0f - a - b, 0.0f);
return (at(i0, j0) * c + at(i0 + 1, j0) * a + at(i0, j0 + 1) * b) / (c + a + b);
}
return at(i0 + 1, j0) * (1.0f - b) + at(i0 + 1, j0 + 1) * (a + b - 1.0f) + at(i0, j0 + 1) * (1.0f - a);
}
};
} // namespace
void MicroStroke::begin(Mesh& m) {
MicroMesh& mm = mutableMicro(m);
mm.ensureTopology(m);
if (mm.dirtyBits.size() != (size_t(mm.baseTriangles) + 63) / 64) mm.dirtyBits.assign((size_t(mm.baseTriangles) + 63) / 64, 0);
tileOf_.assign(mm.baseTriangles, 0);
tiles_.clear();
oldDisp_.clear();
oldMask_.clear();
maskAdded_ = false;
if (dabStamp_.size() != mm.baseTriangles) {
dabStamp_.assign(mm.baseTriangles, 0);
stitchStamp_.assign(mm.baseTriangles, 0);
dabEpoch_ = 0;
}
if (vertStamp_.size() != m.vertexCount()) vertStamp_.assign(m.vertexCount(), 0);
strokeStep_ = mm.step;
grabMirrors_.clear();
grabTris_.clear();
grabWeight_.clear();
grabNormal_.clear();
baseEdge_ = mm.baseEdge;
mm.stroking = true;
active_ = true;
}
// Saves the grids of the triangles in `tris` that this stroke hasn't touched yet.
void MicroStroke::touch(MicroMesh& mm, std::span<const uint32_t> tris) {
if (mm.focus) mm.focus->ensureFull(mm, tris, true); // (edits write full tiles only)
const size_t S = mm.samples, before = tiles_.size();
for (uint32_t t : tris)
if (!tileOf_[t]) {
tiles_.push_back(t);
tileOf_[t] = uint32_t(tiles_.size());
}
if (tiles_.size() == before) return;
oldDisp_.resize(tiles_.size() * S);
if (mm.hasMask()) oldMask_.resize(tiles_.size() * S);
poolFor(tiles_.size() - before, [&](size_t b, size_t e) {
for (size_t i = before + b; i < before + e; ++i) {
const size_t t = tiles_[i];
std::copy_n(mm.disp.data() + t * S, S, oldDisp_.data() + i * S);
if (mm.hasMask()) std::copy_n(mm.mask.data() + t * S, S, oldMask_.data() + i * S);
}
}, 64);
}
// Makes the copies of every shared point of triangles `tris` equal again (see the file comment).
void MicroStroke::stitch(const Mesh& m, MicroMesh& mm, std::span<const uint32_t> tris, const uint8_t* changed) {
const uint32_t n = mm.n, S = mm.samples;
const uint32_t epoch = dabEpoch_;
auto inDab = [&](uint32_t t) { return dabStamp_[t] == epoch; };
if (stitchStamp_.size() != mm.baseTriangles) stitchStamp_.assign(mm.baseTriangles, 0);
auto hit = [&](uint32_t t) { std::atomic_ref<uint32_t>(stitchStamp_[t]).store(epoch, std::memory_order_relaxed); };
// Edges: each shared edge once, by the lower triangle of the two (both in this dab), or copied from a hidden
// neighbour (which brushes leave alone).
poolFor(tris.size(), [&](size_t b, size_t e) {
for (size_t s = b; s < e; ++s) {
const uint32_t t = tris[s];
const glm::uvec3 tt = m.triangles[t];
int16_t* g = mm.disp.data() + size_t(t) * S;
uint8_t* mk = mm.hasMask() ? mm.mask.data() + size_t(t) * S : nullptr;
for (int ed = 0; ed < 3; ++ed) {
const uint32_t nb = mm.edgeNeighbor[size_t(t) * 3 + size_t(ed)];
if (nb == MicroMesh::kNone) continue;
const uint32_t u = nb >> 2;
const int f = int(nb & 3);
const bool hiddenU = m.triangleHidden(u);
if (!(inDab(u) && t < u) && !(hiddenU && !inDab(u))) continue;
int16_t* h = mm.disp.data() + size_t(u) * S;
uint8_t* hk = mk ? mm.mask.data() + size_t(u) * S : nullptr;
const bool reversed = m.triangles[u][f] != tt[ed];
for (uint32_t k = 1; k < n; ++k) {
uint32_t i, j, i2, j2;
MicroMesh::edgePoint(ed, k, n, i, j);
MicroMesh::edgePoint(f, reversed ? n - k : k, n, i2, j2);
const uint32_t a = MicroMesh::index(i, j, n), c = MicroMesh::index(i2, j2, n);
if (hiddenU) {
if (g[a] != h[c] || (mk && mk[a] != hk[c])) hit(t);
g[a] = h[c];
if (mk) mk[a] = hk[c];
} else {
const int16_t v = int16_t((int(g[a]) + int(h[c]) + (int(g[a]) + int(h[c]) >= 0 ? 1 : 0)) / 2);
const uint8_t mv = mk ? uint8_t((int(mk[a]) + int(hk[c]) + 1) / 2) : 0;
if (g[a] != v || (mk && mk[a] != mv)) hit(t);
if (h[c] != v || (mk && hk[c] != mv)) hit(u);
g[a] = h[c] = v;
if (mk) mk[a] = hk[c] = mv;
}
}
}
}
}, 64);
// Corners: every base vertex of these triangles once, averaged over the triangles around it in this dab (or
// taken from a hidden one).
corners_.clear();
const uint32_t vmark = epoch;
for (uint32_t t : tris) {
const glm::uvec3 tt = m.triangles[t];
for (int k = 0; k < 3; ++k)
if (vertStamp_[tt[k]] != vmark) {
vertStamp_[tt[k]] = vmark;
corners_.push_back(tt[k]);
}
}
poolFor(corners_.size(), [&](size_t b, size_t e) {
for (size_t s = b; s < e; ++s) {
const uint32_t v = corners_[s];
const IndexRing ring = m.vertexTriangles(v);
auto cornerIndex = [&](uint32_t u) {
const glm::uvec3 ut = m.triangles[u];
const int c = ut.x == v ? 0 : ut.y == v ? 1 : 2;
return size_t(u) * S + (c == 0 ? 0 : c == 1 ? MicroMesh::index(n, 0, n) : MicroMesh::index(0, n, n));
};
long sum = 0, msum = 0;
int count = 0;
int hiddenValue = 0, hiddenMask = 0;
bool fromHidden = false;
for (uint32_t u : ring) {
const size_t ci = cornerIndex(u);
if (!inDab(u)) {
if (m.triangleHidden(u) && !fromHidden) {
fromHidden = true;
hiddenValue = mm.disp[ci];
hiddenMask = mm.hasMask() ? mm.mask[ci] : 0;
}
continue;
}
sum += mm.disp[ci];
if (mm.hasMask()) msum += mm.mask[ci];
++count;
}
if (!count) continue;
const int16_t value = fromHidden ? int16_t(hiddenValue)
: int16_t((sum + (sum >= 0 ? count / 2 : -(count / 2))) / count);
const uint8_t mval = fromHidden ? uint8_t(hiddenMask) : uint8_t((msum + count / 2) / count);
for (uint32_t u : ring) {
if (!inDab(u)) continue;
const size_t ci = cornerIndex(u);
if (mm.disp[ci] != value || (mm.hasMask() && mm.mask[ci] != mval)) hit(u);
mm.disp[ci] = value;
if (mm.hasMask()) mm.mask[ci] = mval;
}
}
}, 256);
// Ranges (the kernel grew them for what it wrote): stitching averaged shared points with the neighbours, so
// a triangle's edges may now hold its neighbour's larger value.
poolFor(tris.size(), [&](size_t b, size_t e) {
for (size_t s = b; s < e; ++s) {
const uint32_t t = tris[s];
const int16_t* g = mm.disp.data() + size_t(t) * S;
int r = mm.triRange[t];
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);
r = std::max(r, std::abs(int(g[MicroMesh::index(i, j, n)])));
}
mm.triRange[t] = uint16_t(std::min(r, 32767));
}
}, 64);
for (size_t s = 0; s < tris.size(); ++s) {
const uint32_t t = tris[s];
if (changed && !changed[s] && stitchStamp_[t] != epoch) continue; // (nothing of it moved)
mm.rangeMax = std::max(mm.rangeMax, mm.triRange[t]);
mm.markDirty(t);
}
++mm.revision;
}
void MicroStroke::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, const std::function<float(const glm::vec3&)>& texture,
const glm::vec3& strokeDir) {
if (!active_ || !m.micro || radius <= 0.0f) return;
if (!maskBrush && microBrushSupport(type) == 0) return;
auto clock = std::chrono::steady_clock::now();
MicroMesh& mm = *m.micro; // (made unique by begin)
const uint32_t n = mm.n, S = mm.samples;
const float r = radius, r2 = r * r;
const float s = std::clamp(strength, 0.0f, 1.0f);
const float sign = invert ? -1.0f : 1.0f;
// An alpha reaches its square's corners, the square Clay Block tip a little past the circle (as Sculpt.cpp).
const bool useAlpha = alpha && !alpha->empty() && !maskBrush;
const float reach = useAlpha ? kAlphaReach : type == BrushType::ClayBlock && !maskBrush ? 1.3f : 1.0f;
// The displacement range this dab may need: widened first (it costs precision) when what a dab adds could
// pass it; a dab that still clips (planes far off) widens it for the next one.
if (!maskBrush) widen(mm, float(mm.rangeMax) * mm.step + 0.12f * r * s);
// 1. The base triangles within reach.
if (++dabEpoch_ == 0) {
std::fill(dabStamp_.begin(), dabStamp_.end(), 0);
std::fill(stitchStamp_.begin(), stitchStamp_.end(), 0);
std::fill(vertStamp_.begin(), vertStamp_.end(), 0);
dabEpoch_ = 1;
}
microQueryTriangles(m, bvh, center, r * reach, cand_); // (each node grown by the displacement under it)
std::erase_if(cand_, [&](uint32_t t) { return m.triangleHidden(t) || !triangleNear(m, mm, t, center, r * reach); });
if (cand_.empty()) return;
for (uint32_t t : cand_) dabStamp_[t] = dabEpoch_;
if (maskBrush && !mm.hasMask()) {
mm.mask.assign(mm.disp.size(), 0);
oldMask_.assign(tiles_.size() * S, 0); // (the tiles saved so far had no mask: zeros)
maskAdded_ = true;
mm.maskDirty = true;
}
touch(mm, cand_);
findMs += lapMs(clock);
// 2. The brush plane: weighted area normal and centre over every second grid point under the brush.
glm::vec3 areaNormal(0.0f), areaCenter(0.0f);
const bool needPlane = !maskBrush && type != BrushType::Smooth && type != BrushType::Inflate && type != BrushType::Pinch;
if (needPlane) {
const uint32_t stride = n >= 4 ? 2 : 1;
struct Sum {
glm::dvec3 nrm{0.0}, ctr{0.0};
double w = 0.0;
};
const size_t block = 8;
std::vector<Sum> sums((cand_.size() + block - 1) / block);
poolFor(cand_.size(), [&](size_t b, size_t e) {
Sum acc;
MicroTriangle T;
for (size_t ci = b; ci < e; ++ci) {
const uint32_t t = cand_[ci];
T.set(m, t, n);
const int16_t* g = mm.disp.data() + size_t(t) * S;
for (uint32_t j = 0; j <= n; j += stride)
for (uint32_t i = 0; i + j <= n; i += stride) {
glm::vec3 sp, nn;
T.eval(i, j, sp, nn);
const glm::vec3 p = sp + nn * (float(g[MicroMesh::index(i, j, n)]) * mm.step);
const float d2 = glm::dot(p - center, p - center);
if (d2 >= r2) continue;
const float w = brushFalloff(std::sqrt(d2), r, focal);
acc.nrm += glm::dvec3(nn * w);
acc.ctr += glm::dvec3(p * w);
acc.w += w;
}
}
sums[b / block] = acc;
}, block, 2);
Sum total;
for (const Sum& x : sums) total.nrm += x.nrm, total.ctr += x.ctr, total.w += x.w;
if (total.w <= 0.0) {
// nothing under the brush (it only grazed the boxes): the stitch below still runs for the saved tiles
areaNormal = -viewDir;
areaCenter = center;
} else {
areaCenter = glm::vec3(total.ctr / total.w);
const double len = glm::length(total.nrm);
areaNormal = len > 1e-12 ? glm::vec3(total.nrm / len) : -viewDir;
}
}
glm::vec3 up = projectOnPlane(alphaUp, areaNormal);
if (glm::length(up) < 1e-6f)
up = projectOnPlane(std::abs(areaNormal.x) < 0.9f ? glm::vec3(1, 0, 0) : glm::vec3(0, 1, 0), areaNormal);
up = glm::normalize(up);
const glm::vec3 right = glm::cross(up, areaNormal);
const float layerHeight = r * 0.08f * s;
const bool readsNeighbours = type == BrushType::Smooth;
// Pinch, Crease and Sharp Crease pull the surface towards the centre (PinchSampler), reading the grids as the
// dab found them: those it writes copied first.
const bool pinches = !maskBrush && (type == BrushType::Pinch || type == BrushType::Crease || type == BrushType::SharpCrease);
if (pinches) {
if (snapOf_.size() != mm.baseTriangles) snapOf_.assign(mm.baseTriangles, 0);
snap_.resize(cand_.size() * S);
poolFor(cand_.size(), [&](size_t b, size_t e) {
for (size_t ci = b; ci < e; ++ci) {
std::copy_n(mm.disp.data() + size_t(cand_[ci]) * S, S, snap_.data() + ci * S);
snapOf_[cand_[ci]] = uint32_t(ci + 1);
}
}, 64);
}
// Sharp Crease pulls across the stroke only (as on a mesh), so the groove narrows without bunching up along it.
const glm::vec3 alongStroke = glm::length(strokeDir) > 1e-12f ? glm::normalize(strokeDir) : glm::vec3(0.0f);
// 3. The kernel, in parallel over the triangles (each writes only its own grid). Scale-adaptive: the brush is
// evaluated on the grid points `stride` apart, about kBrushSamples across its radius, and the points in between
// get the change interpolated over the coarse micro triangle holding them (a big brush moves big forms; the
// finer displacement rides on top unchanged). Brush evaluation then costs the same at any micro level; what
// grows with the level is only writing the interpolated values.
const float microEdge = baseEdge_ / float(n);
uint32_t stride = 1;
if (adaptive && microEdge > 0.0f)
while (stride < n && microEdge * float(stride * 2) <= r / float(kBrushSamples)) stride *= 2;
lastStride = stride;
const uint32_t cm = n / stride;
std::vector<uint64_t> visited((cand_.size() + 7) / 8, 0);
std::vector<float> clipped((cand_.size() + 7) / 8, 0.0f); // per block: the largest |d| that didn't fit
const float invStep = 1.0f / mm.step;
const PinchSampler pinchSampler{m, mm, snap_.data(), snapOf_.data()};
poolFor(cand_.size(), [&](size_t b, size_t e) {
thread_local std::vector<int16_t> before;
thread_local std::vector<float> coarse;
thread_local std::vector<glm::vec3> coarsePull; // pinches at stride > 1: the pull on the coarse points
thread_local std::vector<glm::vec4> coarsePinch; // ... with the depth change
MicroTriangle T;
uint64_t count = 0;
float over = 0.0f;
for (size_t ci = b; ci < e; ++ci) {
const uint32_t t = cand_[ci];
T.set(m, t, n);
int16_t* g = mm.disp.data() + size_t(t) * S;
uint8_t* mk = mm.hasMask() ? mm.mask.data() + size_t(t) * S : nullptr;
if (readsNeighbours && !maskBrush) before.assign(g, g + S); // Jacobi: neighbours as they were
const int16_t* old = !maskBrush && type == BrushType::Layer ? oldDisp_.data() + size_t(tileOf_[t] - 1) * S : nullptr;
coarse.assign(size_t(cm + 1) * (cm + 2) / 2, 0.0f);
const bool pullCoarse = pinches && stride > 1;
if (pullCoarse) coarsePull.assign(coarse.size(), glm::vec3(0.0f));
bool any = false;
uint32_t cidx = 0;
for (uint32_t cj = 0; cj <= cm; ++cj)
for (uint32_t cii = 0; cii + cj <= cm; ++cii, ++cidx) {
const uint32_t i = cii * stride, j = cj * stride, idx = MicroMesh::index(i, j, n);
glm::vec3 sp, nn;
T.eval(i, j, sp, nn);
const float d = float(g[idx]) * mm.step;
const glm::vec3 p = sp + nn * d;
const glm::vec3 o = p - center;
const float dist2 = glm::dot(o, o);
if (dist2 >= r2 * reach * reach) continue;
++count;
if (maskBrush) {
if (dist2 >= r2) continue;
coarse[cidx] = std::clamp(maskStrength, 0.0f, 1.0f) * brushFalloff(std::sqrt(dist2), r, focal);
any = true;
continue;
}
float f = useAlpha ? alpha->stamp(glm::dot(o, right) / r, glm::dot(o, up) / r, focal)
: brushFalloff(std::sqrt(dist2), r, focal);
if (type == BrushType::ClayBlock && !useAlpha) { // square tip, rounded corners (as Sculpt.cpp)
const float cheb = std::max(std::abs(glm::dot(o, right)), std::abs(glm::dot(o, up))) / r;
const float corner = std::clamp((1.3f - std::sqrt(dist2) / r) / 0.3f, 0.0f, 1.0f);
const float edge = std::clamp((1.0f - cheb) / 0.35f, 0.0f, 1.0f);
f = edge * edge * (3.0f - 2.0f * edge) * corner;
}
if (texture) f *= texture(p);
if (mk && stride == 1) f *= 1.0f - float(mk[idx]) / 255.0f; // (coarse: the fine points' mask, below)
if (f <= 0.0f) continue;
const float facing = std::max(glm::dot(nn, areaNormal), 0.3f); // moving along nn reaches a plane this much slower
float delta = 0.0f;
auto neighbourAverage = [&](float& lo, float& hi) {
float sum = 0.0f;
int c = 0;
lo = 1e30f, hi = -1e30f;
forNeighbors(cii, cj, cm, [&](uint32_t a2, uint32_t b2) {
const float v = float(before[MicroMesh::index(a2 * stride, b2 * stride, n)]);
sum += v, ++c;
lo = std::min(lo, v), hi = std::max(hi, v);
});
return c ? sum / float(c) : float(before[idx]);
};
// The surface pulled by k times its offset from the centre (along the base): the change, in world
// units (at stride > 1 the pull is kept for the write below, which resamples every grid point).
auto pinch = [&](float k, bool across) {
glm::vec3 pull = projectOnPlane(center - p, nn);
if (across) pull -= alongStroke * glm::dot(pull, alongStroke);
if (pullCoarse) {
coarsePull[cidx] = pull * k;
any = any || k != 0.0f;
return 0.0f;
}
const glm::vec3 from = pinchSampler.flat(t, float(i), float(j)) - pull * k;
return (pinchSampler.sample(t, from) - float(pinchSampler.grid(t)[idx])) * mm.step;
};
switch (type) {
case BrushType::Standard: delta = sign * s * r * 0.06f * f * glm::dot(areaNormal, nn); break;
case BrushType::Inflate: delta = sign * s * r * 0.05f * f; break;
case BrushType::Smooth: {
float lo, hi;
const float avg = neighbourAverage(lo, hi);
delta = (avg - float(before[idx])) * mm.step * std::min(1.0f, s * f);
break;
}
case BrushType::Flatten: {
const float h = glm::dot(p - areaCenter, areaNormal);
delta = -h * s * f * (invert ? -0.5f : 1.0f) / facing;
break;
}
case BrushType::Clay: {
const glm::vec3 pp = areaCenter + areaNormal * (sign * r * 0.05f * s);
const float h = glm::dot(p - pp, areaNormal);
if (sign * h < 0.0f) delta = -h * f * clayPull(s) / facing;
break;
}
case BrushType::ClayBlock: {
const glm::vec3 pp = areaCenter + areaNormal * (sign * r * 0.08f * s);
const float h = glm::dot(p - pp, areaNormal);
if (sign * h < 0.0f) delta = -h * f * clayPull(s) / facing;
break;
}
case BrushType::Trim: {
const glm::vec3 pp = areaCenter - areaNormal * (sign * r * 0.02f * s);
const float h = glm::dot(p - pp, areaNormal);
if (sign * h > 0.0f) delta = -h * std::min(1.0f, std::sqrt(f) * (0.5f + s)) / facing;
break;
}
case BrushType::Layer: {
// Up to one height per stroke above where the point started (overlaps never stack).
const float start = float(old[idx]) * mm.step;
const float target = start + sign * layerHeight * f;
delta = sign > 0.0f ? std::max(0.0f, target - d) : std::min(0.0f, target - d);
break;
}
// (the pulls of the mesh brushes, core/SculptKernel.h)
case BrushType::Pinch: delta = pinch(sign * 0.2f * s * f, false); break;
case BrushType::Crease: delta = -sign * s * r * 0.05f * f * f + pinch(0.25f * s * f, false); break;
case BrushType::SharpCrease:
delta = -sign * s * r * 0.08f * f * f * f * f + pinch(0.3f * s * f, true);
break;
default: break;
}
coarse[cidx] = delta;
any = any || delta != 0.0f;
}
if (!any) continue;
// Write: every grid point gets the change interpolated from the coarse points around it (stride 1: its own).
int triMax = mm.triRange[t];
auto apply = [&](uint32_t idx, float delta) {
if (maskBrush) {
const float a = std::clamp(delta, 0.0f, 1.0f);
const float cur = float(mk[idx]) * (1.0f / 255.0f);
const float nv = invert ? cur * (1.0f - a) : cur + (1.0f - cur) * a;
mk[idx] = uint8_t(std::clamp(int(nv * 255.0f + 0.5f), 0, 255));
return;
}
if (stride > 1 && mk) delta *= 1.0f - float(mk[idx]) * (1.0f / 255.0f);
const float nd = float(g[idx]) + delta * invStep; // (in units of the step)
if (std::abs(nd) > 32767.0f) over = std::max(over, std::abs(nd) * mm.step);
const int16_t q = quantizeUnits(nd);
g[idx] = q;
triMax = std::max(triMax, q >= 0 ? int(q) : -int(q));
};
if (stride == 1) {
for (uint32_t k = 0; k < S; ++k)
if (coarse[k] != 0.0f) apply(k, coarse[k]);
} else if (pullCoarse) {
// The depth change and the pull interpolated together; each grid point resampled with its pull.
coarsePinch.resize(coarse.size());
for (size_t k = 0; k < coarse.size(); ++k) coarsePinch[k] = glm::vec4(coarsePull[k], coarse[k]);
const int16_t* own = pinchSampler.grid(t);
forInterpolated(coarsePinch.data(), n, stride, [&](uint32_t idx, uint32_t i, uint32_t j, const glm::vec4& v) {
float delta = v.w;
if (v.x != 0.0f || v.y != 0.0f || v.z != 0.0f) {
const glm::vec3 from = pinchSampler.flat(t, float(i), float(j)) - glm::vec3(v);
delta += (pinchSampler.sample(t, from) - float(own[idx])) * mm.step;
}
if (delta != 0.0f) apply(idx, delta);
});
count += S;
} else {
interpolateCoarse(coarse.data(), n, stride, apply);
count += S;
}
mm.triRange[t] = uint16_t(std::min(triMax, 32767));
}
visited[b / 8] = count;
clipped[b / 8] = over;
}, 8, 2);
for (uint64_t c : visited) points += c;
kernelMs += lapMs(clock);
float over = 0.0f;
for (float c : clipped) over = std::max(over, c);
if (pinches)
for (uint32_t t : cand_) snapOf_[t] = 0;
// 4. Stitch the shared points.
stitch(m, mm, cand_, maskBrush ? nullptr : changed_.data());
if (over > 0.0f) widen(mm, over * 1.5f);
stitchMs += lapMs(clock);
}
void MicroStroke::widen(MicroMesh& mm, float need) {
const int div = mm.widen(need);
if (div == 1) return;
for (int16_t& v : oldDisp_) v = int16_t(int(v) / div);
strokeStep_ = mm.step;
}
void MicroStroke::beginGrab(Mesh& m, const BVH& bvh, const glm::vec3& center, float radius, float focal, const glm::mat3& mirror) {
if (!active_ || !m.micro) return;
MicroMesh& mm = *m.micro;
const uint32_t n = mm.n;
widen(mm, float(mm.rangeMax) * mm.step + radius); // room to move a radius either way
// Scale-adaptive like dab(): the weights on grid points `stride` apart, interpolated in between when moving.
uint32_t stride = 1;
const float microEdge = baseEdge_ / float(n);
if (adaptive && microEdge > 0.0f)
while (stride < n && microEdge * float(stride * 2) <= radius / float(kBrushSamples)) stride *= 2;
lastStride = stride;
const uint32_t cm = n / stride, cs = (cm + 1) * (cm + 2) / 2;
std::vector<uint32_t> cand;
microQueryTriangles(m, bvh, center, radius, cand);
std::erase_if(cand, [&](uint32_t t) { return m.triangleHidden(t) || !triangleNear(m, mm, t, center, radius); });
touch(mm, cand);
GrabMirror gm;
gm.mirror = mirror;
gm.stride = stride;
gm.firstTri = uint32_t(grabTris_.size());
const size_t base = grabWeight_.size();
grabTris_.insert(grabTris_.end(), cand.begin(), cand.end());
grabWeight_.resize(base + cand.size() * cs, 0.0f);
grabNormal_.resize(base + cand.size() * cs, glm::vec3(0.0f));
std::vector<uint8_t> used(cand.size(), 0);
poolFor(cand.size(), [&](size_t b, size_t e) {
MicroTriangle T;
for (size_t k = b; k < e; ++k) {
const uint32_t t = cand[k];
T.set(m, t, n);
const int16_t* g = mm.disp.data() + size_t(t) * mm.samples;
float* w = grabWeight_.data() + base + k * cs;
glm::vec3* nrm = grabNormal_.data() + base + k * cs;
uint32_t c = 0;
for (uint32_t cj = 0; cj <= cm; ++cj)
for (uint32_t ci = 0; ci + cj <= cm; ++ci, ++c) {
const uint32_t i = ci * stride, j = cj * stride;
glm::vec3 sp, nn;
T.eval(i, j, sp, nn);
const glm::vec3 p = sp + nn * (float(g[MicroMesh::index(i, j, n)]) * mm.step);
const float d = glm::distance(p, center);
if (d >= radius) continue;
w[c] = brushFalloff(d, radius, focal);
nrm[c] = nn;
used[k] = 1;
}
}
}, 16);
gm.tris = uint32_t(cand.size());
grabMirrors_.push_back(gm);
for (uint8_t u : used) points += u ? (size_t(cm + 1) * (cm + 2) / 2) : 0;
}
void MicroStroke::grab(Mesh& m, const glm::vec3& delta) {
if (!active_ || !m.micro || grabMirrors_.empty()) return;
auto clock = std::chrono::steady_clock::now();
MicroMesh& mm = *m.micro;
const uint32_t n = mm.n, S = mm.samples;
const float invStep = 1.0f / mm.step;
// One mirror after another (a point may be in two), each in parallel over its triangles.
size_t weightBase = 0;
for (const GrabMirror& gm : grabMirrors_) {
const uint32_t cm = n / gm.stride, cs = (cm + 1) * (cm + 2) / 2;
const glm::vec3 dm = gm.mirror * delta;
poolFor(gm.tris, [&](size_t b, size_t e) {
thread_local std::vector<float> coarse;
coarse.resize(cs);
for (size_t k = b; k < e; ++k) {
const uint32_t t = grabTris_[gm.firstTri + k];
const float* w = grabWeight_.data() + weightBase + k * cs;
const glm::vec3* nrm = grabNormal_.data() + weightBase + k * cs;
bool any = false;
for (uint32_t c = 0; c < cs; ++c) {
coarse[c] = w[c] > 0.0f ? glm::dot(dm, nrm[c]) * w[c] : 0.0f;
any = any || coarse[c] != 0.0f;
}
if (!any) continue;
int16_t* g = mm.disp.data() + size_t(t) * S;
const uint8_t* mk = mm.hasMask() ? mm.mask.data() + size_t(t) * S : nullptr;
int triMax = mm.triRange[t];
interpolateCoarse(coarse.data(), n, gm.stride, [&](uint32_t idx, float dd) {
if (mk) dd *= 1.0f - float(mk[idx]) * (1.0f / 255.0f);
const int16_t q = quantizeUnits(float(g[idx]) + dd * invStep);
g[idx] = q;
triMax = std::max(triMax, q >= 0 ? int(q) : -int(q));
});
mm.triRange[t] = uint16_t(std::min(triMax, 32767));
}
}, 8);
weightBase += size_t(gm.tris) * cs;
}
kernelMs += lapMs(clock);
cand_.clear();
if (++dabEpoch_ == 0) dabEpoch_ = 1;
for (uint32_t t : grabTris_)
if (dabStamp_[t] != dabEpoch_) {
dabStamp_[t] = dabEpoch_;
cand_.push_back(t);
}
stitch(m, mm, cand_);
stitchMs += lapMs(clock);
}
void MicroStroke::restore(Mesh& m) {
if (!active_ || !m.micro || tiles_.empty()) return;
MicroMesh& mm = *m.micro;
const size_t S = mm.samples;
poolFor(tiles_.size(), [&](size_t b, size_t e) {
for (size_t i = b; i < e; ++i) {
const size_t t = tiles_[i];
std::copy_n(oldDisp_.data() + i * S, S, mm.disp.data() + t * S);
if (mm.hasMask() && oldMask_.size() == tiles_.size() * S) std::copy_n(oldMask_.data() + i * S, S, mm.mask.data() + t * S);
}
}, 64);
for (uint32_t t : tiles_) mm.markDirty(t);
++mm.revision;
}
std::unique_ptr<MicroUndo> MicroStroke::end(Mesh& m) {
active_ = false;
if (m.micro) {
m.micro->stroking = false;
if (const uint64_t cap = currentTierConfig().residentCacheCapMB) m.micro->disp.trim(size_t(cap) << 20);
}
grabMirrors_.clear();
grabTris_.clear();
grabWeight_.clear();
grabNormal_.clear();
if (tiles_.empty() || !m.micro) {
tiles_.clear();
return nullptr;
}
auto u = std::make_unique<MicroUndo>();
const MicroMesh& mm = *m.micro;
const size_t S = mm.samples, count = tiles_.size();
u->step = strokeStep_;
u->samples = mm.samples;
for (uint32_t t : tiles_) tileOf_[t] = 0;
// The journal: tiles in Morton order of their centres, each the stroke's change, packed.
AABB box;
for (uint32_t t : tiles_) {
const glm::uvec3 tr = m.triangles[t];
box.expand(m.positions[tr.x]);
}
const glm::vec3 lo = box.min, ext = glm::max(box.extent(), glm::vec3(1e-20f));
auto spread = [](uint32_t x) {
uint64_t v = x & 0x1FFFFF;
v = (v | v << 32) & 0x1F00000000FFFFull;
v = (v | v << 16) & 0x1F0000FF0000FFull;
v = (v | v << 8) & 0x100F00F00F00F00Full;
v = (v | v << 4) & 0x10C30C30C30C30C3ull;
v = (v | v << 2) & 0x1249249249249249ull;
return v;
};
std::vector<std::pair<uint64_t, uint32_t>> order(count);
for (size_t i = 0; i < count; ++i) {
const glm::uvec3 tr = m.triangles[tiles_[i]];
const glm::vec3 c = ((m.positions[tr.x] + m.positions[tr.y] + m.positions[tr.z]) / 3.0f - lo) / ext;
const glm::uvec3 q(glm::clamp(c, 0.0f, 1.0f) * 2097151.0f);
order[i] = {spread(q.x) | spread(q.y) << 1 | spread(q.z) << 2, uint32_t(i)};
}
std::sort(order.begin(), order.end());
std::vector<int16_t> change(count * S), firsts(count);
std::atomic<bool> fits{true};
poolFor(count, [&](size_t b, size_t e) {
for (size_t k = b; k < e; ++k) {
const size_t i = order[k].second;
const int16_t* now = mm.disp.data() + size_t(tiles_[i]) * S;
const int16_t* was = oldDisp_.data() + i * S;
// The change, predicted from the point before it in its row (a row's first point: from the row below;
// the very first is kept apart), so a smooth change needs few bits.
const uint32_t n = mm.n;
uint32_t p = 0;
for (uint32_t j = 0; j <= n; ++j)
for (uint32_t i = 0; i + j <= n; ++i, ++p) {
const int d = int(now[p]) - int(was[p]);
int pred = 0;
if (i > 0) pred = int(now[p - 1]) - int(was[p - 1]);
else if (j > 0) {
const uint32_t q = MicroMesh::index(0, j - 1, n);
pred = int(now[q]) - int(was[q]);
}
const int r = d - pred;
if (r < -32767 || r > 32767) fits = false;
if (p == 0) firsts[k] = int16_t(std::clamp(d, -32767, 32767)), fits = fits && d >= -32767 && d <= 32767;
change[k * S + p] = p == 0 ? int16_t(0) : int16_t(r);
}
}
}, 256);
const bool masked = mm.hasMask() && oldMask_.size() == count * S;
if (fits) {
u->journal = true;
u->tris.resize(count);
u->keys.resize(count);
for (size_t k = 0; k < count; ++k) u->tris[k] = tiles_[order[k].second], u->keys[k] = order[k].first;
microPackTiles(change.data(), count, mm.samples, u->packed);
u->firsts = std::move(firsts);
if (masked) {
u->mask.resize(count * S);
for (size_t k = 0; k < count; ++k)
std::copy_n(oldMask_.data() + size_t(order[k].second) * S, S, u->mask.data() + k * S);
}
} else { // (a change wider than 16 bits: whole old tiles)
u->tris = tiles_;
u->disp = std::move(oldDisp_);
if (masked) u->mask = std::move(oldMask_);
}
u->maskAdded = maskAdded_;
tiles_.clear();
oldDisp_.clear();
oldMask_.clear();
return u;
}
} // namespace sf