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
//
// Kelvinlet brushes (see Kelvinlet.h for the math) and the Detail Clone brush (VDM stamps along a stroke).
#include "core/Kelvinlet.h"
#include "core/Commands.h"
#include "core/Sculpt.h"
#include "core/ThreadPool.h"
#include "core/TierConfig.h"
#include "core/Vdm.h"
#include <algorithm>
#include <array>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <functional>
#include <unordered_map>
#include <vector>
namespace sf {
size_t KelvinletSettings::budget() const {
return vertexBudget ? vertexBudget : std::max<size_t>(size_t(currentTierConfig().activeTriangleBudget / 3), 100000);
}
float KelvinletSettings::poisson() const { return 0.49f * std::clamp(squash, 0.0f, 1.0f); }
// ---------------------------------------------------------------------------
// Kernels
// ---------------------------------------------------------------------------
void KelvinletKernel::grabTerms(float r2, float& A, float& B) const {
A = B = 0.0f;
for (int i = 0; i < scales; ++i) {
const float e2 = eps[i] * eps[i];
const float re2 = r2 + e2;
const float inv = 1.0f / std::sqrt(re2);
const float inv3 = inv * inv * inv;
A += w[i] * ((1.0f - beta) * inv + 0.5f * e2 * inv3);
B += w[i] * (beta * inv3);
}
A *= norm;
B *= norm;
}
float KelvinletKernel::profile(float r2) const {
float t = 0.0f;
for (int i = 0; i < scales; ++i) {
const float e2 = eps[i] * eps[i];
const float re2 = r2 + e2;
const float inv = 1.0f / std::sqrt(re2);
const float inv3 = inv * inv * inv;
t += w[i] * (inv3 + 1.5f * e2 * inv3 * inv * inv);
}
return t * norm;
}
float KelvinletKernel::envelope(float r) const {
const float r2 = r * r;
if (kind == KelvinletKind::Grab) {
float A, B;
grabTerms(r2, A, B);
return std::max(std::abs(A), std::abs(A + B * r2));
}
return std::abs(profile(r2)) * r; // displacement per radian (or per unit log scale) at distance r
}
float KelvinletKernel::cutoff(float amount, float epsilon, float maxDist) const {
if (!(amount > 0.0f) || !(maxDist > 0.0f)) return 0.0f;
// Walk in from the far end: the first sample whose displacement reaches epsilon (the field is not
// monotonic: multi-scale kernels dip slightly below zero before they fade).
constexpr int kSteps = 96;
for (int i = kSteps; i > 0; --i) {
const float r = maxDist * float(i) / float(kSteps);
if (envelope(r) * amount >= epsilon) return std::min(maxDist, r + maxDist / float(kSteps));
}
return maxDist / float(kSteps);
}
KelvinletKernel makeKelvinletKernel(KelvinletKind kind, float radius, const KelvinletSettings& settings, bool tight) {
KelvinletKernel k;
k.kind = kind;
const float nu = settings.poisson();
k.beta = 1.0f / (4.0f * (1.0f - nu));
const float sharp = std::clamp(settings.sharpness, 0.0f, 1.0f);
radius = std::max(radius, 1e-6f);
if (kind == KelvinletKind::Grab && !tight) {
// Tri-scale (1/r^5 far field). The weights cancel the 1/r and 1/r^3 terms of the far field.
const float e1 = 0.75f * radius;
k.scales = 3;
k.eps[0] = e1;
k.eps[1] = 1.5f * e1;
k.eps[2] = 2.25f * e1;
} else {
// Bi-scale: Snake's narrower pull (1/r^3 far field), and Twist / Scale (whose single-scale field already
// falls off as 1/r^3, so the pair falls off as 1/r^5).
const float e1 = (kind == KelvinletKind::Grab ? 0.6f : 0.8f) * radius;
k.scales = 2;
k.eps[0] = e1;
k.eps[1] = 1.5f * e1;
}
// Sharpness: a smaller inner scale gives the cusped, localized peak of the sharp Kelvinlets while the outer
// scales keep the far field (the weights are recomputed, so the far-field terms still cancel).
k.eps[0] *= 1.0f - 0.6f * sharp;
if (k.scales == 3) {
const float a = k.eps[0] * k.eps[0], b = k.eps[1] * k.eps[1], c = k.eps[2] * k.eps[2];
k.w[0] = 1.0f;
k.w[1] = -(c - a) / (c - b);
k.w[2] = (b - a) / (c - b);
} else {
k.w[0] = 1.0f;
k.w[1] = -1.0f;
k.w[2] = 0.0f;
}
// Normalize: K(0) = I for Grab, t(0) = 1 for Twist and Scale.
float at0 = 0.0f;
for (int i = 0; i < k.scales; ++i)
at0 += k.w[i] * (kind == KelvinletKind::Grab ? (1.5f - k.beta) / k.eps[i] : 2.5f / (k.eps[i] * k.eps[i] * k.eps[i]));
k.norm = std::abs(at0) > 1e-30f ? 1.0f / at0 : 0.0f;
return k;
}
glm::vec3 kelvinletGrab(const KelvinletKernel& k, const glm::vec3& r, const glm::vec3& delta) {
float A, B;
k.grabTerms(glm::dot(r, r), A, B);
return A * delta + B * glm::dot(r, delta) * r;
}
glm::vec3 kelvinletTwist(const KelvinletKernel& k, const glm::vec3& r, const glm::vec3& axis, float angle) {
const float theta = angle * k.profile(glm::dot(r, r));
// Rodrigues: an exact rotation of this shell about the axis through the centre.
const float c = std::cos(theta), s = std::sin(theta);
const glm::vec3 rotated = r * c + glm::cross(axis, r) * s + axis * (glm::dot(axis, r) * (1.0f - c));
return rotated - r;
}
glm::vec3 kelvinletScale(const KelvinletKernel& k, const glm::vec3& r, float logScale) {
// Integrates the radial flow dr/dt = s t(r) r (midpoint steps): a pinch never folds a vertex past the centre.
const float len0 = glm::length(r);
if (len0 < 1e-12f) return glm::vec3(0.0f);
const int steps = std::clamp(int(std::ceil(std::abs(logScale) / 0.2f)), 1, 8); // midpoint steps: plenty
const float h = logScale / float(steps);
float len = len0;
for (int i = 0; i < steps; ++i) {
const float mid = len * std::exp(0.5f * h * k.profile(len * len));
len *= std::exp(h * k.profile(mid * mid));
}
return r * (len / len0 - 1.0f);
}
// ---------------------------------------------------------------------------
// The brushes
// ---------------------------------------------------------------------------
namespace {
KelvinletKind kindOf(BrushType type) {
switch (type) {
case BrushType::KelvinTwist: return KelvinletKind::Twist;
case BrushType::KelvinScale: return KelvinletKind::Scale;
default: return KelvinletKind::Grab;
}
}
float window(float r, float cut) {
// 1 inside 70% of the cutoff, then a smoothstep to 0 at the cutoff.
const float t = std::clamp((r - 0.7f * cut) / (0.3f * cut), 0.0f, 1.0f);
return 1.0f - t * t * (3.0f - 2.0f * t);
}
} // namespace
namespace {
// The kernel's radial terms tabulated over u = r^2 / cut^2 (they depend on |r| only), the window folded in: a
// lookup and a lerp per vertex instead of three square roots and divisions per scale.
struct RadialTable {
static constexpr int kSize = 2048;
float scale = 0.0f; // kSize / cut^2
std::vector<float> a, b; // Grab: window * A, window * B; Twist / Scale: profile, window
void build(const KelvinletKernel& k, float cut) {
a.resize(kSize + 2);
b.resize(kSize + 2);
scale = float(kSize) / (cut * cut);
for (int i = 0; i <= kSize + 1; ++i) {
const float r2 = float(std::min(i, kSize)) / scale;
const float w = window(std::sqrt(r2), cut);
if (k.kind == KelvinletKind::Grab) {
float A, B;
k.grabTerms(r2, A, B);
a[size_t(i)] = A * w;
b[size_t(i)] = B * w;
} else {
a[size_t(i)] = k.profile(r2);
b[size_t(i)] = w;
}
}
}
// r2 < cut^2.
void at(float r2, float& outA, float& outB) const {
const float x = r2 * scale;
const int i = std::min(int(x), kSize);
const float t = x - float(i);
outA = a[size_t(i)] + (a[size_t(i) + 1] - a[size_t(i)]) * t;
outB = b[size_t(i)] + (b[size_t(i) + 1] - b[size_t(i)]) * t;
}
};
} // namespace
// ---------------------------------------------------------------------------
// The deferred far field (dense meshes)
// ---------------------------------------------------------------------------
//
// Over a large region, most vertices are in the far field, where the move is a small fraction of the step and
// smooth. There the field (times 1 - the near weight) is added to a coarse lattice in world space, kept once per
// group of vertices (vertex index mod kGroups); each frame one group's vertices take what their lattice gathered
// since their last turn and that lattice starts over. Every vertex gets the near part of every move at once and
// the far part within kGroups frames (all of it when the stroke ends or the pointer rests: flushKelvinletFar).
struct KelvinFarField {
static constexpr int kGroups = 6;
uint64_t stroke = 0;
float h = 0.0f; // lattice spacing (world)
double meshVolume = 1.0; // the model's bounding box volume at the stroke's start
// Spatial groups: blocks of kBlockTriangles consecutive triangles (a compact patch: the renderer's chunks and
// clusters are made of runs of consecutive triangles too), block b in group b % kGroups; a vertex belongs to
// the block of its first triangle (fixed for the stroke: Kelvinlets don't change the topology). So a group's
// turn moves whole patches and dirties few render clusters.
static constexpr uint32_t kBlockShift = 12; // 4096 triangles
std::vector<uint32_t> firstTriangle; // per vertex (its block is its group's)
std::vector<AABB> blockBox; // per block, at the stroke's start, grown by the radius
void prepare(const Mesh& mesh, float margin) {
const size_t nv = mesh.vertexCount(), nt = mesh.triangleCount(), blocks = (nt + (1u << kBlockShift) - 1) >> kBlockShift;
firstTriangle.assign(nv, ~0u);
poolFor(nv, [&](size_t b, size_t e) {
for (size_t v = b; v < e; ++v) {
const IndexRing tris = mesh.vertexTriangles(uint32_t(v));
if (tris.begin() != tris.end()) firstTriangle[v] = *tris.begin();
}
}, 1 << 14);
blockBox.assign(blocks, AABB{});
poolFor(blocks, [&](size_t b, size_t e) {
for (size_t k = b; k < e; ++k) {
AABB box;
const size_t t1 = std::min(nt, (k + 1) << kBlockShift);
for (size_t t = k << kBlockShift; t < t1; ++t)
for (int c = 0; c < 3; ++c) box.expand(mesh.positions[mesh.triangles[t][c]]);
box.min -= glm::vec3(margin);
box.max += glm::vec3(margin);
blockBox[k] = box;
}
}, 16);
}
int turn = 0; // the group whose turn is next
std::unordered_map<uint64_t, uint32_t> index; // lattice point -> slot
std::vector<glm::ivec3> point; // slot -> lattice point
std::vector<std::array<glm::vec3, kGroups>> acc;
std::vector<uint64_t> listed; // slot -> a bit per group: in that group's list since its turn
std::vector<uint32_t> slots[kGroups]; // per group: the slots gathered since its turn
glm::vec3 lo[kGroups], hi[kGroups]; // per group: the bounds of what it gathered since its turn
bool any[kGroups] = {};
static uint64_t key(const glm::ivec3& p) {
return (uint64_t(uint32_t(p.x + (1 << 20)) & 0x1fffff) << 42) | (uint64_t(uint32_t(p.y + (1 << 20)) & 0x1fffff) << 21) |
uint64_t(uint32_t(p.z + (1 << 20)) & 0x1fffff);
}
bool pending() const {
for (bool a : any)
if (a) return true;
return false;
}
};
namespace {
// 1 within half the radius of the load's path, a smoothstep to 0 at the radius: the near field.
float nearWeight(float d, float radius) {
const float t = std::clamp((d - 0.5f * radius) / (0.5f * radius), 0.0f, 1.0f);
return 1.0f - t * t * (3.0f - 2.0f * t);
}
} // namespace
void Sculptor::gatherKelvinletFar(const std::function<glm::vec3(const glm::vec3&)>& displacement, const glm::vec3& a,
const glm::vec3& ab, float radius, const glm::vec3& mid, float reach) {
KelvinFarField& f = *kelvinFar_;
const auto t0 = std::chrono::steady_clock::now();
const float h = f.h;
const glm::ivec3 i0 = glm::ivec3(glm::floor((mid - glm::vec3(reach)) / h));
const glm::ivec3 i1 = glm::ivec3(glm::ceil((mid + glm::vec3(reach)) / h));
const glm::ivec3 dim = i1 - i0 + glm::ivec3(1);
const size_t count = size_t(dim.x) * size_t(dim.y) * size_t(dim.z);
const float ab2 = glm::dot(ab, ab), reach2 = (reach + 1.8f * h) * (reach + 1.8f * h);
std::vector<glm::vec3> value(count, glm::vec3(0.0f));
std::vector<uint8_t> used(count, 0);
poolFor(count, [&](size_t b, size_t e) {
for (size_t i = b; i < e; ++i) {
const glm::ivec3 q = i0 + glm::ivec3(int(i % size_t(dim.x)), int((i / size_t(dim.x)) % size_t(dim.y)),
int(i / (size_t(dim.x) * size_t(dim.y))));
const glm::vec3 p = glm::vec3(q) * h;
if (glm::dot(p - mid, p - mid) > reach2) continue;
const float t = ab2 > 0.0f ? std::clamp(glm::dot(p - a, ab) / ab2, 0.0f, 1.0f) : 0.0f;
const float w = 1.0f - nearWeight(glm::distance(p, a + ab * t), radius);
if (w <= 0.0f) continue;
value[i] = displacement(p) * w;
used[i] = 1;
}
}, 1024);
for (size_t i = 0; i < count; ++i) {
if (!used[i]) continue;
const glm::ivec3 q = i0 + glm::ivec3(int(i % size_t(dim.x)), int((i / size_t(dim.x)) % size_t(dim.y)),
int(i / (size_t(dim.x) * size_t(dim.y))));
auto [it, fresh] = f.index.try_emplace(KelvinFarField::key(q), uint32_t(f.point.size()));
if (fresh) {
f.point.push_back(q);
f.acc.emplace_back();
f.acc.back().fill(glm::vec3(0.0f));
f.listed.push_back(0);
}
const uint32_t slot = it->second;
for (glm::vec3& a : f.acc[slot]) a += value[i];
if (f.listed[slot] != (uint64_t(1) << KelvinFarField::kGroups) - 1) {
for (int g = 0; g < KelvinFarField::kGroups; ++g)
if (!(f.listed[slot] & (uint64_t(1) << g))) f.slots[g].push_back(slot);
f.listed[slot] = (uint64_t(1) << KelvinFarField::kGroups) - 1;
}
}
if (std::getenv("SF_KELVIN_LOG"))
std::fprintf(stderr, "kelvin far: gathered %zu lattice points (%zu in all) in %.1f ms\n", count, f.point.size(),
std::chrono::duration<double, std::milli>(std::chrono::steady_clock::now() - t0).count());
const glm::vec3 lo = glm::vec3(i0) * h, hi = glm::vec3(i1) * h;
for (int g = 0; g < KelvinFarField::kGroups; ++g) {
f.lo[g] = f.any[g] ? glm::min(f.lo[g], lo) : lo;
f.hi[g] = f.any[g] ? glm::max(f.hi[g], hi) : hi;
f.any[g] = true;
}
}
// One group's turn: its vertices in the bounds its lattice gathered take the interpolated field.
void Sculptor::applyKelvinletFarGroup(Mesh& mesh, BVH& bvh, int g) {
KelvinFarField& f = *kelvinFar_;
if (!f.any[g]) return;
auto clock = std::chrono::steady_clock::now();
const float h = f.h;
const glm::ivec3 i0 = glm::ivec3(glm::floor(f.lo[g] / h)), i1 = glm::ivec3(glm::ceil(f.hi[g] / h));
const glm::ivec3 dim = i1 - i0 + glm::ivec3(2);
std::vector<glm::vec3> dense(size_t(dim.x) * size_t(dim.y) * size_t(dim.z), glm::vec3(0.0f));
for (const uint32_t s : f.slots[g]) {
f.listed[s] &= ~(uint64_t(1) << g);
const glm::ivec3 q = f.point[s] - i0;
glm::vec3& v = f.acc[s][size_t(g)];
if (q.x < 0 || q.y < 0 || q.z < 0 || q.x >= dim.x || q.y >= dim.y || q.z >= dim.z) {
v = glm::vec3(0.0f); // (outside every bound gathered since the turn: nothing there)
continue;
}
dense[(size_t(q.z) * size_t(dim.y) + size_t(q.y)) * size_t(dim.x) + size_t(q.x)] = v;
v = glm::vec3(0.0f);
}
f.slots[g].clear();
f.any[g] = false;
const auto& pos = mesh.positions;
const glm::vec3 c = 0.5f * (f.lo[g] + f.hi[g]), ext = f.hi[g] - f.lo[g];
const double volume = double(ext.x) * double(ext.y) * double(ext.z);
const double meshVolume = f.meshVolume; // (measured once per stroke: bounds() reads every vertex)
(void)c;
(void)volume;
(void)meshVolume;
const double denseMs = std::chrono::duration<double, std::milli>(std::chrono::steady_clock::now() - clock).count();
// This group's blocks that meet the bounds it gathered: their triangles' corners that belong to the group.
const size_t nt = mesh.triangleCount(), blocks = f.blockBox.size();
const glm::vec3 lo = f.lo[g], hi = f.hi[g];
std::vector<std::vector<uint32_t>> parts(blocks);
poolFor(blocks, [&](size_t b, size_t e) {
for (size_t k = b; k < e; ++k) {
if (int(k % size_t(KelvinFarField::kGroups)) != g) continue;
const AABB& box = f.blockBox[k];
if (box.max.x < lo.x || box.max.y < lo.y || box.max.z < lo.z || box.min.x > hi.x || box.min.y > hi.y || box.min.z > hi.z)
continue;
auto& out = parts[k];
const size_t t1 = std::min(nt, (k + 1) << KelvinFarField::kBlockShift);
for (size_t t = k << KelvinFarField::kBlockShift; t < t1; ++t)
for (int corner = 0; corner < 3; ++corner) {
const uint32_t v = mesh.triangles[t][corner];
// (each vertex once: from its first triangle, which is in a block of its group)
if (f.firstTriangle[v] == uint32_t(t) && !(mesh.hasHidden() && mesh.vertexHidden(v))) out.push_back(v);
}
}
}, 1);
verts_.clear();
for (const auto& part : parts) verts_.insert(verts_.end(), part.begin(), part.end());
const double selectMs = std::chrono::duration<double, std::milli>(std::chrono::steady_clock::now() - clock).count();
scratch_.resize(verts_.size());
poolFor(verts_.size(), [&](size_t b, size_t e) {
for (size_t i = b; i < e; ++i) {
const glm::vec3 gp = pos[verts_[i]] / h - glm::vec3(i0);
const int x = int(std::floor(gp.x)), y = int(std::floor(gp.y)), z = int(std::floor(gp.z));
if (x < 0 || y < 0 || z < 0 || x >= dim.x - 1 || y >= dim.y - 1 || z >= dim.z - 1) {
scratch_[i] = glm::vec3(0.0f);
continue;
}
const glm::vec3 fr = gp - glm::vec3(float(x), float(y), float(z));
auto at = [&](int dx, int dy, int dz) {
return dense[(size_t(z + dz) * size_t(dim.y) + size_t(y + dy)) * size_t(dim.x) + size_t(x + dx)];
};
const glm::vec3 c00 = glm::mix(at(0, 0, 0), at(1, 0, 0), fr.x), c10 = glm::mix(at(0, 1, 0), at(1, 1, 0), fr.x);
const glm::vec3 c01 = glm::mix(at(0, 0, 1), at(1, 0, 1), fr.x), c11 = glm::mix(at(0, 1, 1), at(1, 1, 1), fr.x);
scratch_[i] = glm::mix(glm::mix(c00, c10, fr.y), glm::mix(c01, c11, fr.y), fr.z);
}
}, 4096);
size_t kept = 0;
const float keep2 = (1e-4f * h) * (1e-4f * h);
for (size_t i = 0; i < verts_.size(); ++i)
if (glm::dot(scratch_[i], scratch_[i]) > keep2) {
verts_[kept] = verts_[i];
scratch_[kept++] = scratch_[i];
}
verts_.resize(kept);
scratch_.resize(kept);
if (std::getenv("SF_KELVIN_LOG"))
std::fprintf(stderr, "kelvin far: group %d, %zu vertices, lattice %.1f, select %.1f, total %.1f ms\n", g, kept, denseMs,
selectMs, std::chrono::duration<double, std::milli>(std::chrono::steady_clock::now() - clock).count());
if (verts_.empty()) return;
displaceAll(mesh, verts_, scratch_);
timings.kernelMs += lapMs(clock);
bvh.refit(mesh, verts_);
timings.bvhMs += lapMs(clock);
timings.vertices += verts_.size();
dabVerts_.insert(dabVerts_.end(), verts_.begin(), verts_.end());
kelvinRingNormals_ = true;
}
bool Sculptor::kelvinletFarPending() const {
return active_ && kelvinFar_ && kelvinFar_->stroke == strokeId_ && kelvinFar_->pending();
}
void Sculptor::flushKelvinletFar(Mesh& mesh, BVH& bvh, bool all) {
if (!kelvinletFarPending()) return;
dabVerts_.clear();
dabLeaves_.clear();
KelvinFarField& f = *kelvinFar_;
for (int i = 0; i < KelvinFarField::kGroups; ++i) {
applyKelvinletFarGroup(mesh, bvh, f.turn);
f.turn = (f.turn + 1) % KelvinFarField::kGroups;
if (!all) break;
}
dabLeaves_.clear();
kelvinRingNormals_ = false;
updateDabNormals(mesh, bvh);
}
void Sculptor::kelvinletSingle(Mesh& mesh, BVH& bvh, const KelvinletKernel& k, const KelvinletStep& s) {
auto clock = std::chrono::steady_clock::now();
float amount = 0.0f, moveScale = 0.0f; // the step's size, and about how far it moves the centre (world)
switch (k.kind) {
case KelvinletKind::Grab: amount = moveScale = glm::length(s.delta); break;
case KelvinletKind::Twist: amount = std::abs(s.angle), moveScale = amount * s.radius; break;
case KelvinletKind::Scale: amount = std::abs(s.logScale), moveScale = amount * s.radius; break;
}
if (!(amount > 0.0f)) return;
if (kelvinStroke_ != strokeId_) { // per stroke: the region size the last move found
kelvinStroke_ = strokeId_;
kelvinLastVerts_ = 0;
kelvinLastCut_ = 0.0f;
}
// Adaptive cutoff: where this step's displacement falls below epsilon = 4% of its largest (the window takes the
// rest smoothly to 0), so a slow drag of tiny steps still moves the surface and a fast one doesn't drag the whole
// mesh into the pass. Over the vertex budget (the last move's density says how many the cutoff will find) the
// fraction rises toward 10%: a tighter region on very dense meshes.
float peak = 0.0f;
for (int i = 0; i <= 32; ++i) peak = std::max(peak, k.envelope(1.5f * s.radius * float(i) / 32.0f));
const glm::vec3 travel0 = k.kind == KelvinletKind::Grab ? (glm::length(s.travel) > 0.0f ? s.travel : s.delta) : glm::vec3(0.0f);
const float maxDist = 3.0f * s.radius;
float fraction = 0.04f;
float cut = k.cutoff(amount, std::max(fraction * amount * peak, 1e-7f * s.radius), maxDist);
const size_t budget = kelvinlet.budget();
if (kelvinLastVerts_ > 0 && kelvinLastCut_ > 0.0f) {
const float reach = cut + 0.5f * glm::length(travel0), lastReach = kelvinLastCut_;
const double predicted = double(kelvinLastVerts_) * double(reach * reach) / double(lastReach * lastReach);
if (predicted > double(budget)) {
fraction = std::min(0.10f, float(0.04 * predicted / double(budget)));
cut = k.cutoff(amount, std::max(fraction * amount * peak, 1e-7f * s.radius), maxDist);
}
}
if (!(cut > 0.0f)) return;
// Grab: the load point travels from `center` to `center + travel` in `substeps` pieces, each a linear Kelvinlet
// applied to where the vertex is by then (forward Euler on the flow), all in one pass: one query, one move,
// one normal and BVH update however far the cursor jumped since the last frame.
const bool grab = k.kind == KelvinletKind::Grab;
const glm::vec3 travel = travel0;
const int n = grab ? std::clamp(s.substeps, 1, 64) : 1;
RadialTable table;
table.build(k, cut);
const float cut2 = cut * cut;
const glm::vec3 dStep = s.delta / float(n), cStep = travel / float(n);
// The displacement of a point that starts at x0 (exact: the kernel through the table).
auto displacement = [&](const glm::vec3& x0) {
glm::vec3 x = x0;
switch (k.kind) {
case KelvinletKind::Grab: {
glm::vec3 c = s.center;
for (int j = 0; j < n; ++j, c += cStep) {
const glm::vec3 r = x - c;
const float r2 = glm::dot(r, r);
if (r2 >= cut2) continue;
float A, B;
table.at(r2, A, B);
x += A * dStep + B * glm::dot(r, dStep) * r;
}
break;
}
case KelvinletKind::Twist: {
const glm::vec3 r = x - s.center;
const float r2 = glm::dot(r, r);
if (r2 >= cut2) break;
float t, w;
table.at(r2, t, w);
const float theta = s.angle * t, co = std::cos(theta), si = std::sin(theta);
const glm::vec3 rot = r * co + glm::cross(s.axis, r) * si + s.axis * (glm::dot(s.axis, r) * (1.0f - co));
x += (rot - r) * w;
break;
}
case KelvinletKind::Scale: {
const glm::vec3 r = x - s.center;
const float r2 = glm::dot(r, r);
if (r2 >= cut2 || r2 < 1e-24f) break;
// The radial flow dr/dt = s t(r) r in midpoint steps, t from the table (clamped at the cutoff).
const int steps = std::clamp(int(std::ceil(amount / 0.2f)), 1, 8);
const float h = s.logScale / float(steps);
const float len0 = std::sqrt(r2), lim = cut2 * 0.999f;
float len = len0, t, w;
for (int j = 0; j < steps; ++j) {
table.at(std::min(len * len, lim), t, w);
const float midLen = len * std::exp(0.5f * h * t);
table.at(std::min(midLen * midLen, lim), t, w);
len *= std::exp(h * t);
}
table.at(r2, t, w);
x += r * ((len / len0 - 1.0f) * w);
break;
}
}
return x - x0;
};
const glm::vec3 mid = s.center + 0.5f * travel;
const float reach = cut + 0.5f * glm::length(travel);
const auto& pos = mesh.positions;
// A region bigger than kelvinlet.deferMinVertices (from the last move's density): the far field goes to the
// lattice (gatherKelvinletFar), only the near field's vertices are moved now.
const float nearReach = s.radius + 0.5f * glm::length(travel);
const bool defer = kelvinLastVerts_ > 0 && kelvinLastCut_ > 0.0f && reach > nearReach &&
double(kelvinLastVerts_) * double(reach * reach) / double(kelvinLastCut_ * kelvinLastCut_) >
double(kelvinlet.deferMinVertices);
if (defer) {
if (!kelvinFar_) kelvinFar_ = std::make_shared<KelvinFarField>();
if (kelvinFar_->stroke != strokeId_) {
*kelvinFar_ = KelvinFarField{};
kelvinFar_->stroke = strokeId_;
kelvinFar_->h = 0.1f * s.radius;
const glm::vec3 e = mesh.bounds().extent();
kelvinFar_->meshVolume = std::max(1e-30, double(e.x) * double(e.y) * double(e.z));
kelvinFar_->prepare(mesh, s.radius);
}
gatherKelvinletFar(displacement, s.center, travel, s.radius, mid, reach);
brushVertices(mesh, bvh, mid, nearReach, verts_);
kelvinLastVerts_ = size_t(double(verts_.size()) * double(reach * reach) / double(nearReach * nearReach));
} else {
brushVertices(mesh, bvh, mid, reach, verts_);
kelvinLastVerts_ = verts_.size();
}
kelvinLastCut_ = reach;
kelvinOverBudget_ = kelvinOverBudget_ || kelvinLastVerts_ > budget;
if (std::getenv("SF_KELVIN_LOG"))
std::fprintf(stderr, "kelvin move: %s, %zu vertices queried, reach %.3f (radius %.3f, travel %.3f), cut %.2f%%\n",
defer ? "near field now" : "all now", verts_.size(), reach, s.radius, glm::length(travel), fraction * 100.0f);
if (verts_.empty()) return;
if (s.frontFacesOnly) {
const auto& nrm = mesh.normals;
std::erase_if(verts_, [&](uint32_t v) { return glm::dot(nrm[v], s.viewDir) > 0.0f; });
if (verts_.empty()) return;
}
scratch_.resize(verts_.size());
if (defer) {
const glm::vec3 a = s.center, ab = travel;
const float ab2 = glm::dot(ab, ab);
poolFor(verts_.size(), [&](size_t b, size_t e) {
for (size_t i = b; i < e; ++i) {
const glm::vec3 x0 = pos[verts_[i]];
const float t = ab2 > 0.0f ? std::clamp(glm::dot(x0 - a, ab) / ab2, 0.0f, 1.0f) : 0.0f;
const float w = nearWeight(glm::distance(x0, a + ab * t), s.radius);
scratch_[i] = w > 0.0f ? displacement(x0) * w : glm::vec3(0.0f);
}
}, 2048);
} else
// Many vertices: the smooth part of the field (beyond half the radius from the load's path) is evaluated on a
// coarse lattice of points around the region and interpolated (trilinear); the near field stays exact. The
// lattice spacing is a fortieth of the region, a tenth of the radius at most: the interpolation error is about
// (h / e)^2 / 8 of the move (well under 1% of it, a fraction of a pixel; tests/test_kelvinlet.cpp checks it).
if (verts_.size() > kelvinlet.proxyMinVertices) {
const float h = std::min(0.06f * s.radius, 2.0f * reach / 48.0f);
const glm::vec3 lo = mid - glm::vec3(reach + h);
const int dim = std::min(128, int(std::ceil(2.0f * (reach + h) / h)) + 2);
const float cell = 2.0f * (reach + h) / float(dim - 1);
std::vector<glm::vec3> lattice(size_t(dim) * size_t(dim) * size_t(dim));
poolFor(lattice.size(), [&](size_t b, size_t e) {
for (size_t i = b; i < e; ++i) {
const size_t ix = i % size_t(dim), iy = (i / size_t(dim)) % size_t(dim), iz = i / (size_t(dim) * size_t(dim));
lattice[i] = displacement(lo + glm::vec3(float(ix), float(iy), float(iz)) * cell);
}
}, 1024);
const float near = (k.kind == KelvinletKind::Scale ? 0.75f : 0.5f) * s.radius + cell;
const glm::vec3 a = s.center, ab = travel;
const float ab2 = glm::dot(ab, ab);
poolFor(verts_.size(), [&](size_t b, size_t e) {
for (size_t i = b; i < e; ++i) {
const glm::vec3 x0 = pos[verts_[i]];
const float t = ab2 > 0.0f ? std::clamp(glm::dot(x0 - a, ab) / ab2, 0.0f, 1.0f) : 0.0f;
if (glm::distance(x0, a + ab * t) < near) {
scratch_[i] = displacement(x0);
continue;
}
const glm::vec3 g = (x0 - lo) / cell;
const int x = std::clamp(int(g.x), 0, dim - 2), y = std::clamp(int(g.y), 0, dim - 2), z = std::clamp(int(g.z), 0, dim - 2);
const glm::vec3 f = glm::clamp(g - glm::vec3(float(x), float(y), float(z)), 0.0f, 1.0f);
auto at = [&](int dx, int dy, int dz) {
return lattice[(size_t(z + dz) * size_t(dim) + size_t(y + dy)) * size_t(dim) + size_t(x + dx)];
};
const glm::vec3 c00 = glm::mix(at(0, 0, 0), at(1, 0, 0), f.x), c10 = glm::mix(at(0, 1, 0), at(1, 1, 0), f.x);
const glm::vec3 c01 = glm::mix(at(0, 0, 1), at(1, 0, 1), f.x), c11 = glm::mix(at(0, 1, 1), at(1, 1, 1), f.x);
scratch_[i] = glm::mix(glm::mix(c00, c10, f.y), glm::mix(c01, c11, f.y), f.z);
}
}, 4096);
} else {
poolFor(verts_.size(), [&](size_t b, size_t e) {
for (size_t i = b; i < e; ++i) scratch_[i] = displacement(pos[verts_[i]]);
}, 2048);
}
// Only what moves noticeably this step goes on (undo, normals, the BVH): the far part of the region moves
// less than 0.5% of the step, which adds up to less than 0.5% of the whole drag.
const float keep = 5e-3f * moveScale, keep2 = keep * keep;
const size_t total = verts_.size();
size_t kept = 0;
for (size_t i = 0; i < total; ++i)
if (glm::dot(scratch_[i], scratch_[i]) > keep2) {
verts_[kept] = verts_[i];
scratch_[kept++] = scratch_[i];
}
verts_.resize(kept);
scratch_.resize(kept);
if (verts_.empty()) return;
displaceAll(mesh, verts_, scratch_);
if (kept * 4 > total) {
finishDab(mesh, bvh, clock); // much of the region moved: refit and renormal the queried leaves
return;
}
timings.kernelMs += lapMs(clock);
bvh.refit(mesh, verts_);
timings.bvhMs += lapMs(clock);
++timings.dabs;
timings.vertices += verts_.size();
dabVerts_.insert(dabVerts_.end(), verts_.begin(), verts_.end());
kelvinRingNormals_ = true; // updateDabNormals: the moved vertices' rings, not every queried leaf
}
void Sculptor::kelvinletStep(Mesh& mesh, BVH& bvh, BrushType type, const KelvinletStep& step, Symmetry sym) {
if (!active_ || !isKelvinletBrush(type) || type == BrushType::DetailClone) return;
const KelvinletKernel k = makeKelvinletKernel(kindOf(type), step.radius, kelvinlet, type == BrushType::KelvinSnake);
kelvinOverBudget_ = false;
dabVerts_.clear();
dabLeaves_.clear();
for (const SymCopy& m : copies(sym)) {
KelvinletStep ms = step;
ms.center = m.point(step.center);
ms.delta = m.dir(step.delta);
ms.travel = m.dir(step.travel);
ms.viewDir = m.dir(step.viewDir);
// The rotation axis is a pseudovector: a mirror flips it once more (det = -1 for an odd mirror count).
ms.axis = m.dir(step.axis) * m.handedness();
kelvinletSingle(mesh, bvh, k, ms);
}
if (kelvinletFarPending()) { // one group of the far field's vertices catches up (see KelvinFarField)
applyKelvinletFarGroup(mesh, bvh, kelvinFar_->turn);
kelvinFar_->turn = (kelvinFar_->turn + 1) % KelvinFarField::kGroups;
}
if (kelvinRingNormals_) dabLeaves_.clear(); // (a mirror that moved little: rings for every mirror's vertices)
kelvinRingNormals_ = false;
updateDabNormals(mesh, bvh);
}
// A plain dab of a Kelvinlet brush (strokes along a path, the Dots stroke, scripts): Grab and Snake follow the
// stroke (a click without motion pulls the surface toward the viewer), Twist turns and Scale pinches by an amount
// set by Intensity per dab (Alt reverses).
void Sculptor::dabKelvinlet(Mesh& mesh, BVH& bvh, BrushType type, const DabParams& p, Symmetry sym) {
if (type == BrushType::DetailClone) {
dabDetailClone(mesh, bvh, p, sym);
return;
}
const float s = std::clamp(p.strength, 0.0f, 1.0f) * std::clamp(p.pressure, 0.0f, 1.0f);
const float sign = p.invert ? -1.0f : 1.0f;
KelvinletStep step;
step.center = p.center;
step.radius = p.radius;
step.viewDir = p.viewDir;
step.frontFacesOnly = p.frontFacesOnly;
step.axis = glm::length(p.viewDir) > 1e-6f ? -glm::normalize(p.viewDir) : glm::vec3(0.0f, 0.0f, 1.0f);
switch (type) {
case BrushType::KelvinGrab:
case BrushType::KelvinSnake: {
if (type == BrushType::KelvinSnake) {
// The multi-scale Snake: the pull narrows as it travels, so drawn-out shapes taper to a tip.
if (snakeStroke_ != strokeId_) {
snakeStroke_ = strokeId_;
snakeTravel_ = 0.0f;
}
snakeTravel_ += glm::length(p.strokeDelta);
step.radius = p.radius * std::max(0.4f, 1.0f / (1.0f + snakeTravel_ / (4.0f * p.radius)));
}
glm::vec3 delta = p.strokeDelta * std::min(1.0f, 2.0f * s);
if (glm::length(p.strokeDelta) < 1e-9f) delta = step.axis * (sign * 0.05f * s * p.radius);
// Small pieces: each one is a linear Kelvinlet, so large moves integrate the flow instead of shearing.
step.delta = delta;
step.travel = glm::length(p.strokeDelta) < 1e-9f ? delta : p.strokeDelta;
step.substeps = std::clamp(int(std::ceil(glm::length(step.travel) / (0.4f * step.radius))), 1, 16);
kelvinletStep(mesh, bvh, type, step, sym);
return;
}
case BrushType::KelvinTwist: step.angle = sign * s * 0.15f; break;
case BrushType::KelvinScale: step.logScale = -sign * s * 0.06f; break; // pinches; Alt swells
default: return;
}
kelvinletStep(mesh, bvh, type, step, sym);
}
// ---------------------------------------------------------------------------
// Detail Clone: the VDM brush's map stamped along the stroke, each stamp turned to follow the stroke
// ---------------------------------------------------------------------------
void Sculptor::cloneStamp(Mesh& mesh, BVH& bvh, const DabParams& p, Symmetry sym) {
dabVerts_.clear();
dabLeaves_.clear();
for (const SymCopy& m : copies(sym)) {
dabVdmSingle(mesh, bvh, transformed(p, m), m.handedness());
}
updateDabNormals(mesh, bvh);
}
void Sculptor::dabDetailClone(Mesh& mesh, BVH& bvh, const DabParams& p, Symmetry sym) {
if (!active_) return;
if (clone_.stroke != strokeId_) {
clone_ = CloneState{};
clone_.stroke = strokeId_;
}
const float r = p.radius;
const float spacing = 2.0f * r * std::clamp(kelvinlet.cloneSpacing, 0.25f, 3.0f);
auto stampAt = [&](DabParams q, const glm::vec3& dir) {
if (kelvinlet.cloneFollowStroke && glm::length(dir) > 1e-9f) q.alphaUp = glm::normalize(dir);
cloneStamp(mesh, bvh, q, sym);
clone_.last = q.center;
clone_.stamped = true;
};
if (!clone_.stamped) {
if (!clone_.pending) { // the first stamp waits for the stroke's direction
clone_.pending = true;
clone_.first = p;
return;
}
const glm::vec3 dir = p.center - clone_.first.center;
if (glm::length(dir) < 0.02f * r) { // dabs in place (scripts, a Dots click held still): stamp as turned
stampAt(clone_.first, glm::vec3(0.0f));
clone_.pending = false;
return;
}
if (glm::length(dir) < 0.25f * r) return; // not far enough yet to say which way the stroke goes
stampAt(clone_.first, dir);
clone_.pending = false;
}
const glm::vec3 d = p.center - clone_.last;
if (glm::length(d) >= spacing) stampAt(p, d);
}
void Sculptor::flushDetailClone(Mesh& mesh, BVH& bvh, Symmetry sym) {
flushKelvinletFar(mesh, bvh, true); // (and the deferred far field of a Kelvinlet stroke)
if (!active_ || clone_.stroke != strokeId_ || !clone_.pending || clone_.stamped) return;
DabParams q = clone_.first;
cloneStamp(mesh, bvh, q, sym);
clone_.pending = false;
clone_.stamped = true;
}
void registerKelvinletCommands(CommandRegistry& registry) {
using T = ParamSpec::Type;
registry.add({"kelvinlet_settings",
"Set the Kelvinlet brushes' material (Brush > Kelvinlet & Capture): Squash (Poisson's ratio: 0 "
"rubbery, 1 incompressible clay that bulges), Sharpness, and Detail Clone's spacing. Unset values stay.",
{{"squash", T::Number, "0-1 (default 0.5).", false},
{"sharpness", T::Number, "0-1: a tighter, cusped peak (default 0).", false},
{"clone_spacing", T::Number, "Detail Clone: stamp spacing in stamp widths, 0.25-3 (default 1).", false},
{"clone_follow", T::Bool, "Detail Clone: stamps turn with the stroke (default true).", false}},
[](Document& doc, const Args& a) -> CommandResult {
KelvinletSettings& k = doc.sculptor.kelvinlet;
k.squash = float(std::clamp(argNumber(a, "squash", k.squash), 0.0, 1.0));
k.sharpness = float(std::clamp(argNumber(a, "sharpness", k.sharpness), 0.0, 1.0));
k.cloneSpacing = float(std::clamp(argNumber(a, "clone_spacing", k.cloneSpacing), 0.25, 3.0));
k.cloneFollowStroke = argBool(a, "clone_follow", k.cloneFollowStroke);
char buf[160];
std::snprintf(buf, sizeof buf, "Kelvinlet: Squash %.0f (Poisson's ratio %.2f), Sharpness %.0f, clone spacing %.2f",
k.squash * 100.0f, k.poisson(), k.sharpness * 100.0f, k.cloneSpacing);
return {true, buf};
}});
}
} // namespace sf