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
//
// Cut: an exact boolean between a mesh and a screen polygon extruded along the view (see Cut.h).
//
// Everything happens in normalised device coordinates (doubles), where the extrusion is a straight prism: walls
// standing on the polygon's edges and two caps at constant depth. Each wall and cap is a "face" of the prism.
// Intersection points come in two kinds, keyed so both sides of every edge find the same one:
// A - a mesh edge crossing a prism face (key: the edge's vertices and the face),
// B - a prism edge piercing a mesh triangle (key: the prism edge and the triangle).
// The segments where a triangle meets a face join those points. Each cut triangle and each prism face is then
// split along its segments into regions (a planar graph, holes bridged, ear-clipped), and every region is kept or
// dropped by which side of the other surface it lies on, read off locally at one of its segments. A mesh vertex
// lying exactly on the prism makes the arrangement degenerate, so the prism is nudged by a tiny random amount (and
// again, a bit more, whenever a test lands too close to call).
#include "core/Cut.h"
#include "core/Commands.h"
#include "core/Masking.h"
#include "core/PaintLayer.h"
#include "core/ScreenSelect.h"
#include "core/Sculpt.h"
#include "core/Document.h"
#include <glm/gtc/matrix_inverse.hpp>
#include <algorithm>
#include <array>
#include <cstdlib>
#include <memory>
#include <cmath>
#include <numeric>
#include <random>
#include <unordered_map>
namespace sf {
const char* cutShapeName(CutShape s) {
switch (s) {
case CutShape::Line: return "line";
case CutShape::Lasso: return "lasso";
case CutShape::Rect: return "rect";
case CutShape::Polyline: return "polyline";
}
return "lasso";
}
const char* cutModeName(CutMode m) {
switch (m) {
case CutMode::Away: return "away";
case CutMode::In: return "in";
case CutMode::Add: return "add";
case CutMode::Clip: return "clip";
}
return "away";
}
bool parseCutShape(const std::string& name, CutShape& out) {
for (CutShape s : {CutShape::Line, CutShape::Lasso, CutShape::Rect, CutShape::Polyline})
if (name == cutShapeName(s)) {
out = s;
return true;
}
if (name == "rectangle") {
out = CutShape::Rect;
return true;
}
return false;
}
bool parseCutMode(const std::string& name, CutMode& out) {
for (CutMode m : {CutMode::Away, CutMode::In, CutMode::Add, CutMode::Clip})
if (name == cutModeName(m)) {
out = m;
return true;
}
return false;
}
namespace {
using glm::dvec2;
using glm::dvec3;
using glm::dvec4;
double cross2(dvec2 a, dvec2 b) { return a.x * b.y - a.y * b.x; }
double orient2(dvec2 a, dvec2 b, dvec2 c) { return cross2(b - a, c - a); }
double signedArea(const std::vector<dvec2>& p) {
double a = 0.0;
for (size_t i = 0; i < p.size(); ++i) a += cross2(p[i], p[(i + 1) % p.size()]);
return 0.5 * a;
}
// Proper crossing of segments ab and cd (not at their ends); `t` = where along ab.
bool segmentsCross(dvec2 a, dvec2 b, dvec2 c, dvec2 d, double& t) {
const double d1 = orient2(c, d, a), d2 = orient2(c, d, b), d3 = orient2(a, b, c), d4 = orient2(a, b, d);
if (!(((d1 > 0) != (d2 > 0)) && ((d3 > 0) != (d4 > 0)))) return false;
if (d1 == 0 || d2 == 0 || d3 == 0 || d4 == 0) return false;
t = d1 / (d1 - d2);
return true;
}
// Removes near-duplicate points, then cuts a self-crossing outline at its first crossing and keeps the larger
// loop, until it is simple. Counter-clockwise on return.
bool simplifyOutline(std::vector<dvec2>& p) {
std::vector<dvec2> q;
for (const dvec2& v : p)
if (q.empty() || glm::length(v - q.back()) > 1e-7) q.push_back(v);
while (q.size() > 1 && glm::length(q.front() - q.back()) <= 1e-7) q.pop_back();
p.swap(q);
for (size_t guard = 0; guard < 4096 && p.size() >= 3; ++guard) {
const size_t n = p.size();
bool crossed = false;
for (size_t i = 0; i < n && !crossed; ++i)
for (size_t j = i + 2; j < n && !crossed; ++j) {
if (i == 0 && j == n - 1) continue; // neighbours through the closing edge
double t;
if (!segmentsCross(p[i], p[(i + 1) % n], p[j], p[(j + 1) % n], t)) continue;
const dvec2 x = p[i] + (p[(i + 1) % n] - p[i]) * t;
std::vector<dvec2> a{x}, b{x};
for (size_t k = i + 1; k <= j; ++k) a.push_back(p[k]);
for (size_t k = j + 1; k < n; ++k) b.push_back(p[k]);
for (size_t k = 0; k <= i; ++k) b.push_back(p[k]);
p = std::abs(signedArea(a)) >= std::abs(signedArea(b)) ? a : b;
crossed = true;
}
if (!crossed) break;
}
if (p.size() < 3) return false;
if (signedArea(p) < 0) std::reverse(p.begin(), p.end());
return std::abs(signedArea(p)) > 1e-10;
}
// A simple polygon with an even-odd inside test, edges bucketed into horizontal bands.
struct Poly2 {
std::vector<dvec2> p;
dvec2 lo{0.0}, hi{0.0};
double bandH = 1.0;
std::vector<std::vector<uint32_t>> bands;
explicit Poly2(std::vector<dvec2> pts) : p(std::move(pts)) {
lo = hi = p[0];
for (const dvec2& v : p) {
lo = glm::min(lo, v);
hi = glm::max(hi, v);
}
const size_t nb = std::clamp<size_t>(p.size(), 1, 1024);
bandH = std::max((hi.y - lo.y) / double(nb), 1e-300);
bands.resize(nb);
for (uint32_t i = 0; i < p.size(); ++i) {
const dvec2 a = p[i], b = p[(i + 1) % p.size()];
const size_t b0 = band(std::min(a.y, b.y)), b1 = band(std::max(a.y, b.y));
for (size_t k = b0; k <= b1; ++k) bands[k].push_back(i);
}
}
size_t band(double y) const {
return size_t(std::clamp((y - lo.y) / bandH, 0.0, double(bands.size() - 1)));
}
bool contains(dvec2 q) const {
if (q.x < lo.x || q.x > hi.x || q.y < lo.y || q.y > hi.y) return false;
bool in = false;
for (uint32_t i : bands[band(q.y)]) {
const dvec2 a = p[i], b = p[(i + 1) % p.size()];
if ((a.y > q.y) != (b.y > q.y) && q.x < a.x + (q.y - a.y) / (b.y - a.y) * (b.x - a.x)) in = !in;
}
return in;
}
};
// --- Planar regions: a polygon split by segments, holes bridged to it --------------------------------------
struct PEdge {
uint32_t a, b;
int32_t tag; // what made the edge (the other surface), -1 = the polygon's own outline or a bridge
};
struct PRegion {
std::vector<uint32_t> cycle; // counter-clockwise, interior on the left
std::vector<int32_t> tags; // tag of edge cycle[i] -> cycle[i + 1]
};
bool planarRegions(const std::vector<dvec2>& p, std::vector<PEdge> edges, std::vector<PRegion>& out) {
out.clear();
const uint32_t n = uint32_t(p.size());
// Drop repeats (keeping a tagged copy) and loops.
{
std::unordered_map<uint64_t, size_t> seen;
std::vector<PEdge> unique;
for (const PEdge& e : edges) {
if (e.a == e.b) continue;
const uint64_t key = (uint64_t(std::min(e.a, e.b)) << 32) | std::max(e.a, e.b);
auto [it, fresh] = seen.emplace(key, unique.size());
if (fresh) unique.push_back(e);
else if (unique[it->second].tag < 0) unique[it->second].tag = e.tag;
}
edges.swap(unique);
}
// Connected pieces; every piece but the outline's (vertex 0) is a hole to bridge.
std::vector<uint32_t> parent(n);
std::iota(parent.begin(), parent.end(), 0u);
auto find = [&](uint32_t x) {
while (parent[x] != x) x = parent[x] = parent[parent[x]];
return x;
};
for (const PEdge& e : edges) parent[find(e.a)] = find(e.b);
std::vector<uint8_t> hasEdge(n, 0);
for (const PEdge& e : edges) hasEdge[e.a] = hasEdge[e.b] = 1;
const uint32_t outer = find(0);
std::unordered_map<uint32_t, uint32_t> leftmost; // piece -> its leftmost vertex
for (uint32_t v = 0; v < n; ++v) {
if (!hasEdge[v] || find(v) == outer) continue;
auto [it, fresh] = leftmost.emplace(find(v), v);
if (!fresh && (p[v].x < p[it->second].x || (p[v].x == p[it->second].x && p[v].y < p[it->second].y))) it->second = v;
}
std::vector<uint32_t> holes;
for (auto& [piece, v] : leftmost) holes.push_back(v);
std::sort(holes.begin(), holes.end(), [&](uint32_t a, uint32_t b) { return p[a].x < p[b].x; });
std::vector<uint8_t> joined(n, 0);
for (uint32_t v = 0; v < n; ++v) joined[v] = hasEdge[v] && find(v) == outer;
for (uint32_t h : holes) {
// Ray to the left: the nearest joined edge it hits, then the vertex there that h sees (as earcut does).
const dvec2 hp = p[h];
double bestX = -1e300;
int best = -1;
for (size_t i = 0; i < edges.size(); ++i) {
const PEdge& e = edges[i];
if (!joined[e.a]) continue;
const dvec2 a = p[e.a], b = p[e.b];
if ((a.y > hp.y) == (b.y > hp.y)) continue;
const double x = a.x + (hp.y - a.y) / (b.y - a.y) * (b.x - a.x);
if (x <= hp.x && x > bestX) {
bestX = x;
best = int(i);
}
}
if (best < 0) return false;
uint32_t m = p[edges[best].a].x < p[edges[best].b].x ? edges[best].a : edges[best].b;
const dvec2 q(bestX, hp.y), mp = p[m];
double bestTan = 1e300;
for (uint32_t v = 0; v < n; ++v) {
if (!joined[v] || v == m) continue;
const dvec2 vp = p[v];
if (vp.x < mp.x || vp.x > hp.x) continue;
const double o1 = orient2(hp, q, vp), o2 = orient2(q, mp, vp), o3 = orient2(mp, hp, vp);
const bool inside = (o1 >= 0 && o2 >= 0 && o3 >= 0) || (o1 <= 0 && o2 <= 0 && o3 <= 0);
if (!inside) continue;
const double tan = std::abs(hp.y - vp.y) / std::max(hp.x - vp.x, 1e-300);
if (tan < bestTan || (tan == bestTan && vp.x > p[m].x)) {
bestTan = tan;
m = v;
}
}
edges.push_back({h, m, -1});
const uint32_t piece = find(h);
for (uint32_t v = 0; v < n; ++v)
if (hasEdge[v] && find(v) == piece) joined[v] = 1;
}
// Half-edges, sorted by angle around each vertex; walking "next clockwise from the twin" traces each region
// counter-clockwise.
struct Half {
uint32_t to;
int32_t tag;
double angle;
};
std::vector<std::vector<Half>> around(n);
for (const PEdge& e : edges) {
around[e.a].push_back({e.b, e.tag, std::atan2(p[e.b].y - p[e.a].y, p[e.b].x - p[e.a].x)});
around[e.b].push_back({e.a, e.tag, std::atan2(p[e.a].y - p[e.b].y, p[e.a].x - p[e.b].x)});
}
for (auto& list : around) std::sort(list.begin(), list.end(), [](const Half& a, const Half& b) { return a.angle < b.angle; });
std::vector<std::vector<uint8_t>> used(n);
for (uint32_t v = 0; v < n; ++v) used[v].assign(around[v].size(), 0);
auto indexOf = [&](uint32_t from, uint32_t to) {
for (size_t i = 0; i < around[from].size(); ++i)
if (around[from][i].to == to) return i;
return size_t(0);
};
for (uint32_t v0 = 0; v0 < n; ++v0)
for (size_t i0 = 0; i0 < around[v0].size(); ++i0) {
if (used[v0][i0]) continue;
PRegion r;
uint32_t v = v0;
size_t i = i0;
for (size_t guard = 0; guard < 4 * edges.size() + 8 && !used[v][i]; ++guard) {
used[v][i] = 1;
const Half& h = around[v][i];
r.cycle.push_back(v);
r.tags.push_back(h.tag);
const uint32_t w = h.to;
const size_t twin = indexOf(w, v), deg = around[w].size();
i = (twin + deg - 1) % deg;
v = w;
}
double area = 0.0;
for (size_t k = 0; k < r.cycle.size(); ++k) area += cross2(p[r.cycle[k]], p[r.cycle[(k + 1) % r.cycle.size()]]);
if (area > 0 && r.cycle.size() >= 3) out.push_back(std::move(r));
}
return true;
}
// Ear clipping of a (weakly) simple counter-clockwise cycle. Never adds vertices, so the outline's edges are
// exactly the triangles' boundary even where the geometry is near-degenerate.
void earClip(const std::vector<dvec2>& p, const std::vector<uint32_t>& cyc, std::vector<std::array<uint32_t, 3>>& out) {
const size_t n = cyc.size();
if (n < 3) return;
std::vector<size_t> prev(n), next(n);
for (size_t i = 0; i < n; ++i) {
prev[i] = (i + n - 1) % n;
next[i] = (i + 1) % n;
}
auto pt = [&](size_t i) { return p[cyc[i]]; };
auto isEar = [&](size_t b) {
const size_t a = prev[b], c = next[b];
const dvec2 pa = pt(a), pb = pt(b), pc = pt(c);
if (orient2(pa, pb, pc) <= 0) return false;
for (size_t j = next[c]; j != a; j = next[j]) {
const uint32_t id = cyc[j];
if (id == cyc[a] || id == cyc[b] || id == cyc[c]) continue;
const dvec2 q = pt(j);
if (orient2(pt(prev[j]), q, pt(next[j])) > 0) continue; // only reflex vertices can block an ear
if (orient2(pa, pb, q) >= 0 && orient2(pb, pc, q) >= 0 && orient2(pc, pa, q) >= 0) return false;
}
return true;
};
size_t count = n, i = 0, stall = 0;
while (count > 3) {
if (isEar(i) || stall > count) {
if (stall > count) { // nothing clean left (near-degenerate): clip the most convex corner
size_t bestI = i;
double best = -1e300;
size_t j = i;
for (size_t k = 0; k < count; ++k, j = next[j]) {
const double o = orient2(pt(prev[j]), pt(j), pt(next[j]));
if (o > best) {
best = o;
bestI = j;
}
}
i = bestI;
}
out.push_back({cyc[prev[i]], cyc[i], cyc[next[i]]});
next[prev[i]] = next[i];
prev[next[i]] = prev[i];
i = prev[i];
--count;
stall = 0;
} else {
i = next[i];
++stall;
}
}
out.push_back({cyc[prev[i]], cyc[i], cyc[next[i]]});
}
// --- The boolean -------------------------------------------------------------------------------------------
enum : uint8_t { kVertex, kA, kB, kCorner };
struct Pt {
dvec3 ndc{0.0};
uint8_t kind = kVertex;
uint32_t u = 0, v = 0; // A: the edge (u < v); B: v = triangle; corner: u = prism corner id
uint32_t e = 0; // B: the prism edge
double lam = 0.0; // A: world-space position along u -> v
dvec3 bary{0.0}; // B: world-space barycentric coordinates in triangle v
};
struct Seg {
uint32_t p, q; // global point ids
uint32_t other; // the prism face (on a triangle) or the triangle (on a face)
};
struct AKeyHash {
size_t operator()(const std::pair<uint64_t, uint32_t>& k) const {
return std::hash<uint64_t>()(k.first * 0x9E3779B97F4A7C15ull ^ k.second);
}
};
struct Cutter {
// Inputs.
const Mesh& mesh;
glm::dmat4 vp, inv;
double s = 1.0; // orientation of the world -> NDC map
std::vector<dvec2> r;
double z0 = 0.0, z1 = 0.0;
bool unionMode = false, caps = true;
// State.
uint32_t nv = 0, n = 0;
std::vector<dvec3> N; // NDC of each vertex
std::vector<double> W; // clip w of each vertex
std::vector<Pt> pts; // the points that aren't mesh vertices (id nv + i)
std::unordered_map<std::pair<uint64_t, uint32_t>, int64_t, AKeyHash> amap; // A key -> point id or -1
std::unordered_map<uint32_t, std::vector<Seg>> triSegs;
std::vector<std::vector<Seg>> faceSegs;
bool degenerate = false;
double eps = 1e-12, baryEps = 1e-11;
// Wall grid.
int G = 1;
dvec2 glo{0.0}, ghi{0.0};
std::vector<std::vector<uint32_t>> cells;
std::unique_ptr<Poly2> poly;
// Output: triangles as global ids, with the mesh triangle they came from (-1 = prism).
std::vector<std::array<uint32_t, 3>> outTris;
std::vector<int64_t> outParent;
std::vector<uint8_t> splitParent; // per mesh triangle: it was cut
size_t removedTriangles = 0, prismTriangles = 0;
explicit Cutter(const Mesh& m) : mesh(m) {}
uint32_t faceCount() const { return n + 2; }
dvec3 ndcOf(uint32_t g) const { return g < nv ? N[g] : pts[g - nv].ndc; }
dvec3 outward(uint32_t f) const {
if (f == n) return {0, 0, -1};
if (f == n + 1) return {0, 0, 1};
const dvec2 e = glm::normalize(r[(f + 1) % n] - r[f]);
return {e.y, -e.x, 0.0};
}
// Signed distance to face f's plane, positive towards the prism's inside.
double dist(uint32_t f, const dvec3& x) const {
if (f == n) return x.z - z0;
if (f == n + 1) return z1 - x.z;
const dvec2 a = r[f], e = r[(f + 1) % n] - a;
return cross2(e, dvec2(x) - a) / glm::length(e);
}
// Whether a point on face f's plane lies on the face.
bool onFace(uint32_t f, const dvec3& x) {
if (f >= n) return poly->contains(dvec2(x));
const dvec2 a = r[f], e = r[(f + 1) % n] - a;
const double t = glm::dot(dvec2(x) - a, e) / glm::dot(e, e);
const double te = baryEps;
if (std::abs(t) < te || std::abs(t - 1) < te || std::abs(x.z - z0) < eps || std::abs(x.z - z1) < eps) degenerate = true;
return t > 0 && t < 1 && x.z > z0 && x.z < z1;
}
bool insidePrism(const dvec3& x) const { return x.z > z0 && x.z < z1 && poly->contains(dvec2(x)); }
// Prism edges: vertical k at corner k, bottom n + k and top 2n + k along wall k. Corners: bottom k, top n + k.
uint32_t cornerId(uint32_t k, bool top) const { return nv + (top ? n : 0) + k % n; }
std::pair<uint32_t, uint32_t> edgeEnds(uint32_t e) const {
if (e < n) return {cornerId(e, false), cornerId(e, true)};
if (e < 2 * n) return {cornerId(e - n, false), cornerId(e - n + 1, false)};
return {cornerId(e - 2 * n, true), cornerId(e - 2 * n + 1, true)};
}
dvec3 unproject(const dvec3& ndc) const {
const dvec4 w = inv * dvec4(ndc, 1.0);
return dvec3(w) / w.w;
}
uint32_t addPoint(const Pt& p) {
pts.push_back(p);
return nv + uint32_t(pts.size() - 1);
}
int cell(double x, double lo, double hi) const {
return std::clamp(int((x - lo) / std::max(hi - lo, 1e-300) * G), 0, G - 1);
}
// The A point where mesh edge (a, b) crosses face f's plane: its id, or -1 when the crossing is off the face.
int64_t aPoint(uint32_t a, uint32_t b, uint32_t f, dvec3& pos) {
const uint32_t u = std::min(a, b), v = std::max(a, b);
const double du = dist(f, N[u]), dv = dist(f, N[v]);
const double t = du / (du - dv);
pos = N[u] + (N[v] - N[u]) * t;
const auto key = std::make_pair((uint64_t(u) << 32) | v, f);
if (auto it = amap.find(key); it != amap.end()) return it->second;
int64_t id = -1;
if (onFace(f, pos)) {
Pt p;
p.ndc = pos;
p.kind = kA;
p.u = u;
p.v = v;
p.lam = t * W[u] / ((1 - t) * W[v] + t * W[u]); // perspective-correct
id = addPoint(p);
}
amap.emplace(key, id);
return id;
}
void processTriangle(uint32_t t) {
const glm::uvec3 tri = mesh.triangles[t];
const dvec3 a = N[tri.x], b = N[tri.y], c = N[tri.z];
const dvec2 lo = glm::min(glm::min(dvec2(a), dvec2(b)), dvec2(c)), hi = glm::max(glm::max(dvec2(a), dvec2(b)), dvec2(c));
const double zmin = std::min({a.z, b.z, c.z}), zmax = std::max({a.z, b.z, c.z});
if (zmax < z0 || zmin > z1 || hi.x < poly->lo.x || lo.x > poly->hi.x || hi.y < poly->lo.y || lo.y > poly->hi.y) return;
// Candidate walls from the grid, then the caps the triangle straddles.
std::vector<uint32_t> faces;
const int x0 = cell(lo.x, glo.x, ghi.x), x1 = cell(hi.x, glo.x, ghi.x);
const int y0 = cell(lo.y, glo.y, ghi.y), y1 = cell(hi.y, glo.y, ghi.y);
for (int y = y0; y <= y1; ++y)
for (int x = x0; x <= x1; ++x)
for (uint32_t k : cells[size_t(y) * G + x]) faces.push_back(k);
std::sort(faces.begin(), faces.end());
faces.erase(std::unique(faces.begin(), faces.end()), faces.end());
const size_t walls = faces.size();
if (zmin < z0 && zmax > z0) faces.push_back(n);
if (zmin < z1 && zmax > z1) faces.push_back(n + 1);
if (faces.empty()) return;
const dvec3 rn = glm::cross(b - a, c - a);
const double rn2 = glm::dot(rn, rn);
if (rn2 <= 0) return;
// B points: the prism edges of the candidate walls that pierce the triangle.
std::vector<std::pair<uint32_t, uint32_t>> pierced; // (prism edge, point id)
std::vector<uint32_t> tried;
auto pierce = [&](uint32_t e) {
if (std::find(tried.begin(), tried.end(), e) != tried.end()) return;
tried.push_back(e);
const auto [i0, i1] = edgeEnds(e);
const dvec3 p0 = pts[i0 - nv].ndc, p1 = pts[i1 - nv].ndc;
const double d0 = glm::dot(rn, p0 - a), d1 = glm::dot(rn, p1 - a);
const double scale = std::sqrt(rn2) * eps;
if (std::abs(d0) < scale || std::abs(d1) < scale) {
// A prism corner on the triangle's plane: only a problem when it is on the triangle.
const dvec3 x = std::abs(d0) < scale ? p0 : p1;
const double l0 = glm::dot(glm::cross(b - x, c - x), rn) / rn2, l1 = glm::dot(glm::cross(c - x, a - x), rn) / rn2;
if (l0 > -baryEps && l1 > -baryEps && 1 - l0 - l1 > -baryEps) degenerate = true;
return;
}
if ((d0 > 0) == (d1 > 0)) return;
const dvec3 x = p0 + (p1 - p0) * (d0 / (d0 - d1));
const double l0 = glm::dot(glm::cross(b - x, c - x), rn) / rn2;
const double l1 = glm::dot(glm::cross(c - x, a - x), rn) / rn2;
const double l2 = 1.0 - l0 - l1;
if (std::abs(l0) < baryEps || std::abs(l1) < baryEps || std::abs(l2) < baryEps) degenerate = true;
if (l0 <= 0 || l1 <= 0 || l2 <= 0) return;
Pt p;
p.ndc = x;
p.kind = kB;
p.e = e;
p.v = t;
const dvec3 wl(l0 / W[tri.x], l1 / W[tri.y], l2 / W[tri.z]);
p.bary = wl / (wl.x + wl.y + wl.z);
pierced.push_back({e, addPoint(p)});
};
for (size_t i = 0; i < walls; ++i) {
const uint32_t k = faces[i];
for (uint32_t e : {k, (k + 1) % n, n + k, 2 * n + k}) pierce(e);
}
const uint32_t vi[3] = {tri.x, tri.y, tri.z};
for (uint32_t f : faces) {
double d[3];
for (int i = 0; i < 3; ++i) {
d[i] = dist(f, N[vi[i]]);
if (std::abs(d[i]) < eps) degenerate = true;
}
if ((d[0] > 0) == (d[1] > 0) && (d[1] > 0) == (d[2] > 0)) continue;
// The two triangle edges the plane crosses.
struct X {
dvec3 pos;
int64_t id;
} xs[2];
int nx = 0;
for (int i = 0; i < 3 && nx < 2; ++i) {
const int j = (i + 1) % 3;
if ((d[i] > 0) == (d[j] > 0)) continue;
xs[nx].id = aPoint(vi[i], vi[j], f, xs[nx].pos);
++nx;
}
if (nx != 2) {
degenerate = true;
return;
}
// The face's own edges through the triangle.
std::vector<std::pair<double, uint32_t>> bs;
const dvec3 dir = xs[1].pos - xs[0].pos;
const double dd = glm::dot(dir, dir);
for (const auto& [e, id] : pierced) {
const bool mine = f < n ? (e == f || e == (f + 1) % n || e == n + f || e == 2 * n + f)
: (f == n ? (e >= n && e < 2 * n) : e >= 2 * n);
if (mine) bs.push_back({dd > 0 ? glm::dot(pts[id - nv].ndc - xs[0].pos, dir) / dd : 0.0, id});
}
if (xs[0].id < 0 && xs[1].id < 0 && bs.empty()) continue;
std::sort(bs.begin(), bs.end());
bool in = xs[0].id >= 0;
uint32_t cur = in ? uint32_t(xs[0].id) : 0;
auto seg = [&](uint32_t p, uint32_t q) {
triSegs[t].push_back({p, q, f});
faceSegs[f].push_back({p, q, t});
};
for (const auto& [param, id] : bs) {
if (in) seg(cur, id);
else cur = id;
in = !in;
}
if (in != (xs[1].id >= 0)) {
degenerate = true;
return;
}
if (in) seg(cur, uint32_t(xs[1].id));
}
}
// Splits one mesh triangle along its segments; keeps the regions outside the prism.
void splitTriangle(uint32_t t, const std::vector<Seg>& segs) {
const glm::uvec3 tri = mesh.triangles[t];
const uint32_t vi[3] = {tri.x, tri.y, tri.z};
const dvec3 rn = glm::cross(N[tri.y] - N[tri.x], N[tri.z] - N[tri.x]);
// 2D frame: drop the normal's largest axis, keeping counter-clockwise = rn.
int axis = 0;
if (std::abs(rn.y) > std::abs(rn[axis])) axis = 1;
if (std::abs(rn.z) > std::abs(rn[axis])) axis = 2;
int ia = (axis + 1) % 3, ib = (axis + 2) % 3;
if (rn[axis] < 0) std::swap(ia, ib);
std::vector<uint32_t> ids;
std::unordered_map<uint32_t, uint32_t> local;
auto loc = [&](uint32_t g) {
auto [it, fresh] = local.emplace(g, uint32_t(ids.size()));
if (fresh) ids.push_back(g);
return it->second;
};
for (uint32_t v : vi) loc(v);
std::vector<PEdge> edges;
// Outline: each side with the A points on it, in order.
for (int i = 0; i < 3; ++i) {
const uint32_t u = vi[i], w = vi[(i + 1) % 3];
std::vector<std::pair<double, uint32_t>> on;
for (const Seg& s : segs)
for (uint32_t g : {s.p, s.q})
if (g >= nv && pts[g - nv].kind == kA && pts[g - nv].u == std::min(u, w) && pts[g - nv].v == std::max(u, w))
on.push_back({glm::dot(pts[g - nv].ndc - N[u], N[w] - N[u]), g});
std::sort(on.begin(), on.end());
on.erase(std::unique(on.begin(), on.end()), on.end());
uint32_t prev = loc(u);
for (const auto& [param, g] : on) {
const uint32_t l = loc(g);
edges.push_back({prev, l, -1});
prev = l;
}
edges.push_back({prev, loc(w), -1});
}
for (const Seg& s : segs) edges.push_back({loc(s.p), loc(s.q), int32_t(s.other)});
std::vector<dvec2> p2(ids.size());
for (size_t i = 0; i < ids.size(); ++i) {
const dvec3 x = ndcOf(ids[i]);
p2[i] = {x[ia], x[ib]};
}
std::vector<PRegion> regions;
if (!planarRegions(p2, edges, regions)) {
degenerate = true;
return;
}
std::vector<std::array<uint32_t, 3>> tris;
for (const PRegion& reg : regions) {
int which = -1;
for (size_t k = 0; k < reg.tags.size() && which < 0; ++k)
if (reg.tags[k] >= 0) which = int(k);
if (which < 0) {
degenerate = true;
return;
}
const dvec3 P = ndcOf(ids[reg.cycle[which]]), Q = ndcOf(ids[reg.cycle[(which + 1) % reg.cycle.size()]]);
const bool inside = glm::dot(glm::cross(rn, Q - P), outward(uint32_t(reg.tags[which]))) < 0;
if (inside) continue;
tris.clear();
earClip(p2, reg.cycle, tris);
for (const auto& tr : tris) {
outTris.push_back({ids[tr[0]], ids[tr[1]], ids[tr[2]]});
outParent.push_back(t);
}
}
}
// Face f's outline: its prism edges in order (counter-clockwise around its outward normal), with direction.
std::vector<std::pair<uint32_t, bool>> faceEdges(uint32_t f) const {
std::vector<std::pair<uint32_t, bool>> out; // (edge, forward)
if (f < n) {
out = {{n + f, true}, {(f + 1) % n, true}, {2 * n + f, false}, {f, false}};
} else if (f == n + 1) {
for (uint32_t k = 0; k < n; ++k) out.push_back({2 * n + k, true});
} else {
for (uint32_t k = n; k-- > 0;) out.push_back({n + k, false});
}
return out;
}
dvec2 face2d(uint32_t f, const dvec3& x) const {
if (f == n + 1) return {x.x, x.y};
if (f == n) return {x.x, -x.y};
const dvec2 a = r[f], e = glm::normalize(r[(f + 1) % n] - a);
return {glm::dot(dvec2(x) - a, e), x.z};
}
// Splits face f along its segments. Returns, per prism edge on its outline with no B points, the status of the
// region along it (1 inside the mesh, 0 outside) in `edgeStatus`. Keeps the regions the mode wants.
void splitFace(uint32_t f, std::vector<int8_t>& edgeStatus) {
const std::vector<Seg>& segs = faceSegs[f];
std::vector<uint32_t> ids;
std::unordered_map<uint32_t, uint32_t> local;
auto loc = [&](uint32_t g) {
auto [it, fresh] = local.emplace(g, uint32_t(ids.size()));
if (fresh) ids.push_back(g);
return it->second;
};
std::vector<PEdge> edges;
std::vector<std::pair<uint64_t, uint32_t>> plainEdges; // (local a, local b) -> prism edge, for edgeStatus
const auto outline = faceEdges(f);
loc(outline.empty() ? 0 : (outline[0].second ? edgeEnds(outline[0].first).first : edgeEnds(outline[0].first).second));
for (const auto& [e, fwd] : outline) {
const auto [e0, e1] = edgeEnds(e);
const uint32_t from = fwd ? e0 : e1, to = fwd ? e1 : e0;
const dvec3 A = pts[from - nv].ndc, B = pts[to - nv].ndc;
std::vector<std::pair<double, uint32_t>> on;
for (const Seg& s : segs)
for (uint32_t g : {s.p, s.q})
if (g >= nv && pts[g - nv].kind == kB && pts[g - nv].e == e) on.push_back({glm::dot(pts[g - nv].ndc - A, B - A), g});
std::sort(on.begin(), on.end());
on.erase(std::unique(on.begin(), on.end()), on.end());
uint32_t prev = loc(from);
for (const auto& [param, g] : on) {
const uint32_t l = loc(g);
edges.push_back({prev, l, -1});
prev = l;
}
edges.push_back({prev, loc(to), -1});
if (on.empty()) plainEdges.push_back({(uint64_t(loc(from)) << 32) | loc(to), e});
}
for (const Seg& s : segs) edges.push_back({loc(s.p), loc(s.q), int32_t(s.other)});
std::vector<dvec2> p2(ids.size());
for (size_t i = 0; i < ids.size(); ++i) p2[i] = face2d(f, ndcOf(ids[i]));
std::vector<PRegion> regions;
if (!planarRegions(p2, edges, regions)) {
degenerate = true;
return;
}
const dvec3 out = outward(f);
std::vector<std::array<uint32_t, 3>> tris;
for (const PRegion& reg : regions) {
int which = -1;
for (size_t k = 0; k < reg.tags.size() && which < 0; ++k)
if (reg.tags[k] >= 0) which = int(k);
if (which < 0) {
degenerate = true;
return;
}
const uint32_t t = uint32_t(reg.tags[which]);
const glm::uvec3 tri = mesh.triangles[t];
const dvec3 nt = s * glm::cross(N[tri.y] - N[tri.x], N[tri.z] - N[tri.x]);
const dvec3 P = ndcOf(ids[reg.cycle[which]]), Q = ndcOf(ids[reg.cycle[(which + 1) % reg.cycle.size()]]);
const bool insideMesh = glm::dot(glm::cross(out, Q - P), nt) < 0;
for (size_t k = 0; k < reg.cycle.size(); ++k) {
const uint64_t key = (uint64_t(reg.cycle[k]) << 32) | reg.cycle[(k + 1) % reg.cycle.size()];
for (const auto& [pk, e] : plainEdges)
if (pk == key) edgeStatus[e] = insideMesh ? 1 : 0;
}
if (insideMesh == unionMode) continue;
tris.clear();
earClip(p2, reg.cycle, tris);
emitPrism(ids, tris);
}
}
void emitPrism(const std::vector<uint32_t>& ids, const std::vector<std::array<uint32_t, 3>>& tris) {
// Counter-clockwise around the outward normal in NDC; the world winding flips with s, and a difference
// keeps the prism's inside-out surface.
const bool flip = unionMode ? s < 0 : s > 0;
for (const auto& tr : tris) {
if (flip) outTris.push_back({ids[tr[0]], ids[tr[2]], ids[tr[1]]});
else outTris.push_back({ids[tr[0]], ids[tr[1]], ids[tr[2]]});
outParent.push_back(-1);
++prismTriangles;
}
}
// Winding number of the mesh around an NDC point (1 inside a closed mesh, 0 outside).
double winding(const dvec3& x) const {
double sum = 0.0;
for (const glm::uvec3& tri : mesh.triangles) {
const dvec3 A = N[tri.x] - x, B = N[tri.y] - x, C = N[tri.z] - x;
const double la = glm::length(A), lb = glm::length(B), lc = glm::length(C);
const double num = glm::dot(A, glm::cross(B, C));
const double den = la * lb * lc + glm::dot(A, B) * lc + glm::dot(B, C) * la + glm::dot(C, A) * lb;
sum += 2.0 * std::atan2(num, den);
}
return s * sum / (4.0 * 3.14159265358979323846);
}
// One attempt; false when degenerate (try again with another nudge).
bool run() {
pts.clear();
amap.clear();
triSegs.clear();
outTris.clear();
outParent.clear();
degenerate = false;
removedTriangles = prismTriangles = 0;
n = uint32_t(r.size());
poly = std::make_unique<Poly2>(r);
faceSegs.assign(faceCount(), {});
for (uint32_t k = 0; k < 2 * n; ++k) {
Pt p;
p.kind = kCorner;
p.u = k;
p.ndc = dvec3(r[k % n], k < n ? z0 : z1);
addPoint(p);
}
// Wall grid over the shape's box, clipped to the mesh's.
dvec2 mlo(1e300), mhi(-1e300);
for (const dvec3& x : N) {
mlo = glm::min(mlo, dvec2(x));
mhi = glm::max(mhi, dvec2(x));
}
glo = glm::max(poly->lo, mlo);
ghi = glm::min(poly->hi, mhi);
G = std::clamp(int(std::sqrt(double(n)) * 2.0), 4, 256);
cells.assign(size_t(G) * G, {});
for (uint32_t k = 0; k < n; ++k) {
const dvec2 a = r[k], b = r[(k + 1) % n];
const int x0 = cell(std::min(a.x, b.x), glo.x, ghi.x), x1 = cell(std::max(a.x, b.x), glo.x, ghi.x);
const int y0 = cell(std::min(a.y, b.y), glo.y, ghi.y), y1 = cell(std::max(a.y, b.y), glo.y, ghi.y);
if (std::max(a.x, b.x) < glo.x || std::min(a.x, b.x) > ghi.x || std::max(a.y, b.y) < glo.y || std::min(a.y, b.y) > ghi.y)
continue;
for (int y = y0; y <= y1; ++y)
for (int x = x0; x <= x1; ++x) cells[size_t(y) * G + x].push_back(k);
}
const uint32_t nt = uint32_t(mesh.triangleCount());
for (uint32_t t = 0; t < nt && !degenerate; ++t) processTriangle(t);
if (degenerate) return false;
splitParent.assign(nt, 0);
for (auto& [t, segs] : triSegs) {
splitParent[t] = 1;
++removedTriangles; // counted again below if a piece survives; only used to tell "nothing happened"
splitTriangle(t, segs);
if (degenerate) return false;
}
const bool anySegments = !triSegs.empty();
// Untouched triangles: entirely on one side.
for (uint32_t t = 0; t < nt; ++t) {
if (splitParent[t]) continue;
const glm::uvec3 tri = mesh.triangles[t];
if (insidePrism((N[tri.x] + N[tri.y] + N[tri.z]) / 3.0)) {
++removedTriangles;
continue;
}
outTris.push_back({tri.x, tri.y, tri.z});
outParent.push_back(t);
}
if (!caps) return true;
// Prism faces: split the cut ones; the rest take the status of a neighbour across an uncut edge.
std::vector<int8_t> edgeStatus(3 * n, -1);
std::vector<int8_t> faceStatus(faceCount(), -1);
for (uint32_t f = 0; f < faceCount(); ++f)
if (!faceSegs[f].empty()) {
splitFace(f, edgeStatus);
if (degenerate) return false;
faceStatus[f] = 2; // done
}
if (!anySegments) {
const int8_t st = winding(pts[0].ndc) > 0.5 ? 1 : 0;
std::fill(faceStatus.begin(), faceStatus.end(), st);
}
for (bool changed = true; changed;) {
changed = false;
for (uint32_t f = 0; f < faceCount(); ++f) {
if (faceStatus[f] != -1) continue;
for (const auto& [e, fwd] : faceEdges(f))
if (edgeStatus[e] >= 0) {
faceStatus[f] = edgeStatus[e];
changed = true;
break;
}
if (faceStatus[f] >= 0)
for (const auto& [e, fwd] : faceEdges(f)) edgeStatus[e] = faceStatus[f];
}
}
for (uint32_t f = 0; f < faceCount(); ++f) {
if (faceStatus[f] == 2) continue;
if (faceStatus[f] < 0) return false;
if ((faceStatus[f] == 1) == unionMode) continue;
std::vector<uint32_t> ids, cyc;
std::vector<dvec2> p2;
for (const auto& [e, fwd] : faceEdges(f)) {
const auto [e0, e1] = edgeEnds(e);
ids.push_back(fwd ? e0 : e1);
cyc.push_back(uint32_t(cyc.size()));
p2.push_back(face2d(f, pts[ids.back() - nv].ndc));
}
std::vector<std::array<uint32_t, 3>> tris;
earClip(p2, cyc, tris);
emitPrism(ids, tris);
}
return true;
}
};
// Removes the zero-area triangles a cut can leave where the prism runs along a surface it already made (a symmetric
// cut whose mirror image overlaps it, a second cut through an earlier cap): a needle (two corners at one point)
// collapses its short edge, a cap (a corner on the opposite side) flips that side with the triangle across it. The
// next cut skipped such triangles and cracked (Discord, dm4nd: "the cap sometimes fails to close"). `pos` gives an
// id's position. Keeps the triangles as they were unless the result is still closed and manifold.
template <class Pos>
void cleanSlivers(std::vector<std::array<uint32_t, 3>>& tris, std::vector<int64_t>& parents, std::vector<uint8_t>& touched,
const Pos& pos) {
constexpr double kFlat = 1e-6; // twice the area / the longest side squared
constexpr double kShort = 1e-5; // the shortest side / the longest
auto key = [](uint32_t a, uint32_t b) { return (uint64_t(a) << 32) | b; };
std::vector<std::array<uint32_t, 3>> T = tris;
std::vector<int64_t> P = parents;
std::vector<int64_t> changedParents;
bool any = false;
for (int pass = 0; pass < 8; ++pass) {
std::unordered_map<uint64_t, uint32_t> edge;
edge.reserve(T.size() * 3);
for (uint32_t t = 0; t < T.size(); ++t)
for (int i = 0; i < 3; ++i) edge[key(T[t][i], T[t][(i + 1) % 3])] = t;
std::unordered_map<uint32_t, uint32_t> collapse; // id -> the id it merges into
std::vector<uint8_t> dead(T.size(), 0), busy(T.size(), 0);
bool changed = false;
for (uint32_t t = 0; t < T.size(); ++t) {
if (busy[t]) continue;
const dvec3 p[3] = {pos(T[t][0]), pos(T[t][1]), pos(T[t][2])};
double len[3];
for (int i = 0; i < 3; ++i) len[i] = glm::length(p[(i + 1) % 3] - p[i]); // side i: corner i -> i + 1
const int lo = int(std::min_element(len, len + 3) - len), hi = int(std::max_element(len, len + 3) - len);
if (len[hi] <= 0.0) continue;
if (glm::length(glm::cross(p[1] - p[0], p[2] - p[0])) > kFlat * len[hi] * len[hi]) continue;
if (len[lo] < kShort * len[hi]) { // needle: side lo's end merges into its start
const uint32_t a = T[t][lo], b = T[t][(lo + 1) % 3];
if (a == b || collapse.count(a) || collapse.count(b)) continue;
collapse[b] = a;
busy[t] = 1;
changed = true;
continue;
}
// cap: side hi (a -> b) has c on it; the triangle across it is (b, a, d)
const uint32_t a = T[t][hi], b = T[t][(hi + 1) % 3], c = T[t][(hi + 2) % 3];
const auto it = edge.find(key(b, a));
if (it == edge.end() || busy[it->second]) continue;
const uint32_t o = it->second;
uint32_t d = ~0u;
for (int i = 0; i < 3; ++i)
if (T[o][i] == b && T[o][(i + 1) % 3] == a) d = T[o][(i + 2) % 3];
if (d == ~0u || d == c || edge.count(key(c, d)) || edge.count(key(d, c))) continue;
const int64_t parent = P[o];
changedParents.push_back(P[t]);
changedParents.push_back(P[o]);
T[t] = {a, d, c};
T[o] = {d, b, c};
P[t] = P[o] = parent;
busy[t] = busy[o] = 1;
changed = true;
}
if (!collapse.empty()) {
auto root = [&](uint32_t g) {
for (auto it = collapse.find(g); it != collapse.end() && it->second != g; it = collapse.find(g)) g = it->second;
return g;
};
std::vector<std::array<uint32_t, 3>> keptT;
std::vector<int64_t> keptP;
for (uint32_t t = 0; t < T.size(); ++t) {
std::array<uint32_t, 3> r = {root(T[t][0]), root(T[t][1]), root(T[t][2])};
if (r != T[t]) changedParents.push_back(P[t]);
if (r[0] == r[1] || r[1] == r[2] || r[2] == r[0]) continue; // the needle and its twin across the short side
keptT.push_back(r);
keptP.push_back(P[t]);
}
T.swap(keptT);
P.swap(keptP);
}
any = any || changed;
if (!changed) break;
}
if (!any || T.empty()) return;
// Closed and manifold still: every directed side once, with its twin.
std::unordered_map<uint64_t, int> count;
count.reserve(T.size() * 3);
for (const auto& t : T)
for (int i = 0; i < 3; ++i) count[key(t[i], t[(i + 1) % 3])] += 1;
for (const auto& [k, n] : count) {
const auto twin = count.find((k << 32) | (k >> 32));
if (n != 1 || twin == count.end() || twin->second != 1) return;
}
tris.swap(T);
parents.swap(P);
for (int64_t p : changedParents)
if (p >= 0 && size_t(p) < touched.size()) touched[size_t(p)] = 1; // (its corners come from the weights now)
}
bool closedMesh(const Mesh& mesh) {
std::unordered_map<uint64_t, int> count;
count.reserve(mesh.triangleCount() * 3);
for (const glm::uvec3& t : mesh.triangles)
for (int i = 0; i < 3; ++i) {
const uint32_t a = t[i], b = t[(i + 1) % 3];
count[(uint64_t(a) << 32) | b] += 1;
}
for (const auto& [key, c] : count) {
const uint64_t twin = (key << 32) | (key >> 32);
auto it = count.find(twin);
if (c != 1 || it == count.end() || it->second != 1) return false;
}
return !mesh.triangles.empty();
}
} // namespace
bool isWatertight(const Mesh& mesh) { return closedMesh(mesh); }
bool cutRegion(CutShape shape, const std::vector<glm::vec2>& points, bool flip, bool closed,
std::vector<glm::dvec2>& region, std::string& error) {
region.clear();
constexpr double kFar = 1000.0; // NDC: far beyond any visible model
auto side = [&](dvec2 d) { return flip ? dvec2(d.y, -d.x) : dvec2(-d.y, d.x); };
if (shape == CutShape::Line || (shape == CutShape::Polyline && !closed)) {
std::vector<dvec2> p;
for (const glm::vec2& v : points)
if (p.empty() || glm::length(dvec2(v) - p.back()) > 1e-6) p.push_back(dvec2(v));
if (shape == CutShape::Line && p.size() > 2) p = {p.front(), p.back()};
if (p.size() < 2) {
error = "Cut: draw a line (two different points)";
return false;
}
const dvec2 d0 = glm::normalize(p[1] - p[0]), d1 = glm::normalize(p.back() - p[p.size() - 2]);
const dvec2 start = p.front() - d0 * kFar, end = p.back() + d1 * kFar;
region.push_back(start);
if (shape == CutShape::Polyline) region.insert(region.end(), p.begin(), p.end()); // (a line's are on the way)
region.push_back(end);
region.push_back(end + side(d1) * kFar);
region.push_back(start + side(d0) * kFar);
} else {
for (const glm::vec2& v : points) region.push_back(dvec2(v));
if (shape == CutShape::Rect && region.size() == 2) {
const dvec2 a = region[0], b = region[1];
region = {a, {b.x, a.y}, b, {a.x, b.y}};
}
if (region.size() < 3) {
error = "Cut: the shape needs at least three points";
return false;
}
}
if (!simplifyOutline(region)) {
error = "Cut: the shape encloses no area";
return false;
}
return true;
}
size_t clipMesh(Mesh& mesh, const glm::mat4& viewProj, const std::vector<glm::dvec2>& region,
const std::vector<glm::dvec2>& outline, bool open) {
const glm::dmat4 vp(viewProj), inv = glm::inverse(vp);
const size_t segments = open ? outline.size() - 1 : outline.size();
if (outline.size() < 2 || region.size() < 3) return 0;
auto inside = [&](dvec2 q) { // even-odd
bool in = false;
for (size_t i = 0, j = region.size() - 1; i < region.size(); j = i++) {
const dvec2 a = region[i], b = region[j];
if ((a.y > q.y) != (b.y > q.y) && q.x < (b.x - a.x) * (q.y - a.y) / (b.y - a.y) + a.x) in = !in;
}
return in;
};
auto nearest = [&](dvec2 q) {
dvec2 best = outline[0];
double bestD = 1e300;
for (size_t i = 0; i < segments; ++i) {
const dvec2 a = outline[i], b = outline[(i + 1) % outline.size()], ab = b - a;
const double len2 = glm::dot(ab, ab);
const double t = len2 > 0.0 ? std::clamp(glm::dot(q - a, ab) / len2, 0.0, 1.0) : 0.0;
const dvec2 p = a + ab * t;
const double d = glm::dot(q - p, q - p);
if (d < bestD) {
bestD = d;
best = p;
}
}
return best;
};
const bool layers = !mesh.layers.empty();
std::vector<uint32_t> moved;
for (uint32_t v = 0; v < mesh.vertexCount(); ++v) {
const float weight = 1.0f - mesh.maskAt(v);
if (weight <= 0.0f || (mesh.hasHidden() && mesh.vertexHidden(v))) continue;
const glm::dvec4 c = vp * glm::dvec4(dvec3(mesh.positions[v]), 1.0);
if (c.w <= 1e-12) continue; // behind the camera
const dvec3 ndc = dvec3(c) / c.w;
if (inside(dvec2(ndc)) != open) continue;
const dvec2 to = nearest(dvec2(ndc));
glm::dvec4 w = inv * glm::dvec4(to, ndc.z, 1.0);
const glm::vec3 target = glm::vec3(dvec3(w) / w.w);
const glm::vec3 d = (target - mesh.positions[v]) * weight;
if (glm::dot(d, d) <= 0.0f) continue;
mesh.positions[v] += d;
if (layers) mesh.base[v] += d;
moved.push_back(v);
}
if (!moved.empty()) mesh.recomputeAllNormals();
return moved.size();
}
bool cutMesh(const Mesh& mesh, const glm::mat4& viewProj, const std::vector<glm::dvec2>& region, CutMode mode,
float depth, Mesh& out, std::string& error, const Mesh* depthFrom) {
if (mesh.triangleCount() == 0) {
error = "Cut: the Part is empty";
return false;
}
if (region.size() < 3) {
error = "Cut: the shape needs at least three points";
return false;
}
Cutter c(mesh);
c.vp = glm::dmat4(viewProj);
c.inv = glm::inverse(c.vp);
c.s = glm::determinant(c.vp) < 0 ? -1.0 : 1.0;
c.nv = uint32_t(mesh.vertexCount());
c.N.resize(c.nv);
c.W.resize(c.nv);
double zmin = 1e300, zmax = -1e300;
dvec2 lo(1e300), hi(-1e300);
for (uint32_t v = 0; v < c.nv; ++v) {
const dvec4 clip = c.vp * dvec4(dvec3(mesh.positions[v]), 1.0);
if (clip.w <= 1e-12) {
error = "Cut: part of the Part is behind the camera; step back and try again";
return false;
}
c.W[v] = clip.w;
c.N[v] = dvec3(clip) / clip.w;
zmin = std::min(zmin, c.N[v].z);
zmax = std::max(zmax, c.N[v].z);
lo = glm::min(lo, dvec2(c.N[v]));
hi = glm::max(hi, dvec2(c.N[v]));
}
const double extent = std::max({hi.x - lo.x, hi.y - lo.y, 1e-9});
c.eps = 1e-12 * std::max(1.0, extent);
const bool closed = closedMesh(mesh);
c.unionMode = mode == CutMode::Add;
c.caps = closed;
if (c.unionMode && !closed) {
error = "Cut Add needs a closed (watertight) Part; remesh it first";
return false;
}
// Depth range of the extrusion, measured on `depthFrom` when given (the Part before a symmetric cut's first copy,
// so a mirror image that overlaps it starts from the same surface, not from the pocket the first one made).
const Mesh& dm = depthFrom ? *depthFrom : mesh;
std::vector<dvec3> dN;
if (depthFrom) {
dN.resize(dm.vertexCount());
for (size_t v = 0; v < dN.size(); ++v) {
const dvec4 clip = c.vp * dvec4(dvec3(dm.positions[v]), 1.0);
dN[v] = clip.w > 1e-12 ? dvec3(clip) / clip.w : dvec3(1e300); // (behind the camera: under no shape)
}
}
const std::vector<dvec3>& DN = depthFrom ? dN : c.N;
const Poly2 shape(region);
double zFront = 1e300, zBack = -1e300;
dvec3 frontHit(0.0), backHit(0.0); // world points of the nearest and farthest surface under the shape
for (uint32_t v = 0; v < uint32_t(DN.size()); ++v)
if (shape.contains(dvec2(DN[v]))) {
if (DN[v].z < zFront) {
zFront = DN[v].z;
frontHit = dvec3(dm.positions[v]);
}
if (DN[v].z > zBack) {
zBack = DN[v].z;
backHit = dvec3(dm.positions[v]);
}
}
// A shape inside one big triangle covers no vertex: also sample the surface under the shape's corners and
// centre (front and back hits, interpolated in the triangles there).
{
std::vector<dvec2> samples;
const size_t stride = std::max<size_t>(1, region.size() / 48);
dvec2 centre(0.0);
for (size_t i = 0; i < region.size(); ++i) {
centre += region[i];
if (i % stride == 0 && shape.contains(region[i] * 0.999 + region[(i + 1) % region.size()] * 0.0005 +
region[(i + region.size() - 1) % region.size()] * 0.0005))
samples.push_back(region[i]);
}
centre /= double(region.size());
if (shape.contains(centre)) samples.push_back(centre);
for (uint32_t t = 0; t < dm.triangleCount(); ++t) {
const glm::uvec3 tri = dm.triangles[t];
const dvec3 a = DN[tri.x], b = DN[tri.y], cc = DN[tri.z];
const double area = orient2(dvec2(a), dvec2(b), dvec2(cc));
if (area == 0.0) continue;
const dvec2 tlo = glm::min(glm::min(dvec2(a), dvec2(b)), dvec2(cc)), thi = glm::max(glm::max(dvec2(a), dvec2(b)), dvec2(cc));
for (const dvec2& q : samples) {
if (q.x < tlo.x || q.x > thi.x || q.y < tlo.y || q.y > thi.y) continue;
const double l0 = orient2(dvec2(b), dvec2(cc), q) / area, l1 = orient2(dvec2(cc), dvec2(a), q) / area;
const double l2 = 1.0 - l0 - l1;
if (l0 < 0 || l1 < 0 || l2 < 0) continue;
const double z = l0 * a.z + l1 * b.z + l2 * cc.z;
if (z < zFront) {
zFront = z;
frontHit = c.unproject(dvec3(q, z));
}
if (z > zBack) {
zBack = z;
backHit = c.unproject(dvec3(q, z));
}
}
}
}
const double margin = 1e-3 * std::max(zmax - zmin, 1e-6);
double z0 = zmin - margin, z1 = zmax + margin;
if (mode != CutMode::Away) {
AABB box;
for (const glm::vec3& p : dm.positions) box.expand(p);
const double size = double(std::max({box.extent().x, box.extent().y, box.extent().z}));
const double d = std::clamp(double(depth), 1e-4, 4.0) * size;
const dvec3 forward = glm::normalize(c.unproject({0, 0, 0.5}) - c.unproject({0, 0, -0.5}));
auto ndcZ = [&](const dvec3& p, bool& ok) {
const dvec4 clip = c.vp * dvec4(p, 1.0);
ok = clip.w > 1e-12;
return clip.z / clip.w;
};
bool ok = true;
if (zFront > 1e299) {
if (mode == CutMode::In) {
error = "Cut: the shape misses the Part";
return false;
}
const dvec3 mid = dvec3(box.center());
z0 = ndcZ(mid - forward * (d * 0.5), ok);
z1 = ndcZ(mid + forward * (d * 0.5), ok);
} else if (mode == CutMode::In) {
z1 = ndcZ(frontHit + forward * d, ok);
} else {
const dvec3 pf = frontHit, pb = backHit;
z0 = ndcZ(pf - forward * d, ok);
z1 = std::max(ndcZ((pf + pb) * 0.5, ok), ndcZ(pf + forward * (d * 0.25), ok));
}
if (!ok || !(z1 > z0)) {
error = "Cut: the depth reaches past the camera; lower Depth or step back";
return false;
}
}
std::mt19937 rng(12345);
for (int attempt = 0; attempt < 8; ++attempt) {
const double amp = 1e-7 * extent * std::pow(3.0, attempt); // at most ~2e-4 of the view
std::uniform_real_distribution<double> jitter(-amp, amp);
c.r = region;
for (dvec2& p : c.r) p += dvec2(jitter(rng), jitter(rng));
c.z0 = z0 + jitter(rng) * 1e-3;
c.z1 = z1 + jitter(rng) * 1e-3;
if (!c.run()) continue;
if (closed)
cleanSlivers(c.outTris, c.outParent, c.splitParent, [&](uint32_t g) {
return g < c.nv ? dvec3(mesh.positions[g]) : c.unproject(c.pts[g - c.nv].ndc);
});
// Output vertices: every id the triangles use, in order.
std::vector<uint32_t> remap(c.nv + c.pts.size(), ~0u), used;
for (const auto& t : c.outTris)
for (uint32_t g : t)
if (remap[g] == ~0u) {
remap[g] = uint32_t(used.size());
used.push_back(g);
}
const bool changed = c.prismTriangles > 0 || c.outTris.size() != mesh.triangleCount() || used.size() != mesh.vertexCount();
if (!changed) {
error = "Cut: the shape misses the Part";
return false;
}
if (c.outTris.empty()) {
error = "Cut: that would remove the whole Part";
return false;
}
Mesh m;
const size_t nvOut = used.size(), ntOut = c.outTris.size();
m.positions.resize(nvOut);
const bool hasLayers = !mesh.layers.empty();
if (hasLayers) {
m.base.resize(nvOut);
m.layers = mesh.layers;
for (SculptLayer& l : m.layers) l.delta.assign(nvOut, glm::vec3(0.0f));
}
if (mesh.hasMask()) m.mask.assign(nvOut, 0.0f);
glm::vec3 capColor(1.0f);
if (mesh.hasColors()) {
m.colors.assign(nvOut, glm::vec3(1.0f));
glm::dvec3 sum(0.0);
size_t k = 0;
for (const Pt& p : c.pts)
if (p.kind == kA) {
sum += dvec3(glm::mix(mesh.colors[p.u], mesh.colors[p.v], float(p.lam)));
++k;
}
if (k) capColor = glm::vec3(sum / double(k));
}
std::vector<uint32_t> kept(nvOut, 0);
// Weights of the source vertices for each output vertex.
auto weights = [&](uint32_t g, std::array<std::pair<uint32_t, float>, 3>& w) {
if (g < c.nv) {
w = {{{g, 1.0f}, {g, 0.0f}, {g, 0.0f}}};
return true;
}
const Pt& p = c.pts[g - c.nv];
if (p.kind == kA) {
w = {{{p.u, float(1 - p.lam)}, {p.v, float(p.lam)}, {p.v, 0.0f}}};
return true;
}
if (p.kind == kB) {
const glm::uvec3 tri = mesh.triangles[p.v];
w = {{{tri.x, float(p.bary.x)}, {tri.y, float(p.bary.y)}, {tri.z, float(p.bary.z)}}};
return true;
}
return false;
};
const std::vector<glm::vec3>& base = mesh.basePositions();
for (size_t i = 0; i < nvOut; ++i) {
const uint32_t g = used[i];
std::array<std::pair<uint32_t, float>, 3> w;
if (!weights(g, w)) { // a prism corner
m.positions[i] = glm::vec3(c.unproject(c.pts[g - c.nv].ndc));
if (hasLayers) m.base[i] = m.positions[i];
if (mesh.hasColors()) m.colors[i] = capColor;
continue;
}
glm::dvec3 pos(0.0), bp(0.0);
float best = -1.0f;
for (const auto& [v, wt] : w) {
pos += dvec3(mesh.positions[v]) * double(wt);
if (hasLayers) bp += dvec3(base[v]) * double(wt);
if (wt > best) {
best = wt;
kept[i] = v;
}
}
m.positions[i] = glm::vec3(pos);
if (hasLayers) {
m.base[i] = glm::vec3(bp);
for (size_t l = 0; l < m.layers.size(); ++l) {
glm::vec3 d(0.0f);
for (const auto& [v, wt] : w) d += mesh.layers[l].delta[v] * wt;
m.layers[l].delta[i] = d;
}
}
if (mesh.hasMask()) {
float mk = 0.0f;
for (const auto& [v, wt] : w) mk += mesh.mask[v] * wt;
m.mask[i] = mk;
}
if (mesh.hasColors()) {
glm::vec3 col(0.0f);
for (const auto& [v, wt] : w) col += mesh.colors[v] * wt;
m.colors[i] = col;
}
}
m.triangles.resize(ntOut);
uint32_t capGroup = 0;
if (c.prismTriangles > 0) {
for (uint32_t gid : mesh.facegroups) capGroup = std::max(capGroup, gid);
capGroup += 1;
m.ensureFaceGroups(0);
} else if (mesh.hasFaceGroups()) {
m.facegroups.resize(ntOut);
}
if (mesh.hasHidden()) m.hidden.assign(ntOut, 0);
if (mesh.hasUvs()) m.uvs.assign(ntOut * 3, glm::vec2(0.0f));
if (mesh.hasUvFlags()) m.uvFlags.assign(ntOut * 3, 0);
std::vector<uint32_t> newIndex(mesh.triangleCount(), Mesh::kNoQuad);
for (size_t t = 0; t < ntOut; ++t) {
const auto& tr = c.outTris[t];
m.triangles[t] = glm::uvec3(remap[tr[0]], remap[tr[1]], remap[tr[2]]);
const int64_t parent = c.outParent[t];
if (parent < 0) {
if (!m.facegroups.empty()) m.facegroups[t] = capGroup;
continue;
}
const uint32_t pt = uint32_t(parent);
if (!m.facegroups.empty()) m.facegroups[t] = mesh.facegroupAt(pt);
if (mesh.hasHidden()) m.hidden[t] = mesh.hidden[pt];
if (!c.splitParent[pt]) {
newIndex[pt] = uint32_t(t);
if (mesh.hasUvs())
for (int k = 0; k < 3; ++k) m.uvs[t * 3 + k] = mesh.uvs[pt * 3 + k];
if (mesh.hasUvFlags())
for (int k = 0; k < 3; ++k) m.uvFlags[t * 3 + k] = mesh.uvFlags[pt * 3 + k];
continue;
}
if (mesh.hasUvs()) {
const glm::uvec3 src = mesh.triangles[pt];
for (int k = 0; k < 3; ++k) {
std::array<std::pair<uint32_t, float>, 3> w;
if (!weights(tr[k], w)) continue;
glm::vec2 uv(0.0f);
for (const auto& [v, wt] : w)
for (int j = 0; j < 3; ++j)
if (src[j] == v) uv += mesh.uvs[pt * 3 + j] * wt;
m.uvs[t * 3 + k] = uv;
}
}
}
if (mesh.hasQuads()) remapQuads(mesh, newIndex, m);
m.texture = mesh.texture;
m.paintToTexture = mesh.paintToTexture;
m.selectionSets = mesh.selectionSets;
if (!mesh.paintLayers.empty()) copyPaintLayers(mesh, m, kept);
m.rebuildTopology();
m.recomputeAllNormals();
m.sanitizeAttributes();
if (closed && !closedMesh(m)) continue; // a crack: try again with another nudge
out = std::move(m);
return true;
}
error = "Cut: the shape runs too close to the Part's vertices; draw it again slightly differently";
return false;
}
// --- Command -----------------------------------------------------------------------------------------------
void registerCutCommands(CommandRegistry& registry) {
using T = ParamSpec::Type;
registry.add(
{"cut",
"Cut the active Part with a shape drawn on the screen (Line, Lasso, Rectangle or Polyline), extruded along "
"the view. Modes: away (remove what the shape covers, through the whole Part, and close it with a flat cap), "
"in (cut a flat-bottomed pocket `depth` deep), add (add the shape extruded `depth` out of the surface), clip "
"(remove nothing: press what lies on the shaded side of a line, or outside a closed shape, flat onto the "
"shape's outline, like a clip brush). The result stays watertight. Coordinates are normalised (-1..1, y up) in the given view; without a view the "
"shape is drawn on the Part seen from the front (+Z).",
{{"shape", T::String, "line, lasso, rect or polyline. Default lasso.", false},
{"points", T::String, "The shape's points \"x0 y0 x1 y1 ...\": two for a line (or a rect's corners), three or "
"more for a lasso, two or more for a polyline.", true},
{"mode", T::String, "away, in, add or clip. Default away.", false},
{"depth", T::Number, "In and add: how deep or tall, as a fraction of the Part's size (0.001-4). Default 0.1.", false},
{"flip", T::Bool, "Line and open polyline: cut the right side instead of the left. Default false.", false},
{"closed", T::Bool, "Polyline: a closed polygon (cuts its inside) instead of a bent line. Default false.", false},
{"view_proj", T::String, "Optional 16 numbers: column-major view-projection matrix.", false},
{"symmetry", T::String, "Mirror axes, e.g. \"x\": the mirror image of the shape cuts too (default none).", false}},
[](Document& doc, const Args& a) -> CommandResult {
if (doc.mesh.triangleCount() == 0) return {false, "The Part is empty"};
if (!doc.mesh.forgespheres.empty()) return {false, "Cut: make Forge Spheres into a mesh first"};
if (!doc.mesh.tube.empty()) return {false, "Cut: bake the Tube first"};
if (doc.mesh.micro) return {false, "Cut: apply or remove the micro level first"};
CutShape shape = CutShape::Lasso;
CutMode mode = CutMode::Away;
if (!parseCutShape(argString(a, "shape", "lasso"), shape)) return {false, "Cut: shape is line, lasso, rect or polyline"};
if (!parseCutMode(argString(a, "mode", "away"), mode)) return {false, "Cut: mode is away, in, add or clip"};
std::vector<glm::vec2> points;
{
const std::string text = argString(a, "points");
std::vector<float> nums;
const char* s = text.c_str();
char* end = nullptr;
for (float v = std::strtof(s, &end); end != s; v = std::strtof(s, &end)) {
nums.push_back(v);
s = end;
}
for (size_t i = 0; i + 1 < nums.size(); i += 2) points.push_back({nums[i], nums[i + 1]});
if (nums.size() % 2) return {false, "Cut: points are x y pairs"};
}
std::string error;
glm::mat4 vp;
if (!viewProjArg(doc.mesh, a, vp, error)) return {false, error};
std::vector<SymCopy> copies;
if (!symmetryCopiesArg(a, doc.mesh, copies, error)) return {false, error};
if (copies.empty()) copies.push_back(SymCopy{});
std::vector<glm::dvec2> region;
if (!cutRegion(shape, points, argBool(a, "flip", false), argBool(a, "closed", false), region, error))
return {false, error};
if (mode == CutMode::Clip) {
// The outline the vertices are pressed onto: a line or open polyline runs on far past its ends.
const bool open = shape == CutShape::Line || (shape == CutShape::Polyline && !argBool(a, "closed", false));
std::vector<glm::dvec2> outline;
for (const glm::vec2& p : points)
if (outline.empty() || glm::length(glm::dvec2(p) - outline.back()) > 1e-6) outline.push_back(glm::dvec2(p));
if (shape == CutShape::Line && outline.size() > 2) outline = {outline.front(), outline.back()};
if (shape == CutShape::Rect && outline.size() == 2) {
const glm::dvec2 p = outline[0], q = outline[1];
outline = {p, {q.x, p.y}, q, {p.x, q.y}};
}
if (open) {
const glm::dvec2 d0 = glm::normalize(outline[1] - outline[0]);
const glm::dvec2 d1 = glm::normalize(outline.back() - outline[outline.size() - 2]);
outline.front() -= d0 * 1000.0;
outline.back() += d1 * 1000.0;
}
Mesh m = doc.mesh;
size_t moved = 0;
for (const SymCopy& copy : copies) {
glm::mat4 inv(glm::transpose(copy.m));
inv[3] = glm::vec4(copy.pivot - glm::transpose(copy.m) * copy.pivot, 1.0f);
moved += clipMesh(m, vp * inv, region, outline, open);
}
if (moved == 0) return {true, "Clip: the shape misses the Part"};
doc.replaceMeshUndoable(std::move(m), "Clip");
return {true, "Clip: " + std::to_string(moved) + " vertices pressed flat"};
}
const float depth = float(argNumber(a, "depth", 0.1));
// A mirror image of the shape that lands on the shape itself (a rectangle across the mirror plane) would
// cut the same prism twice: skip it.
auto sameCutter = [&](const glm::mat4& a, const glm::mat4& b) {
const glm::dmat4 A(a), invB = glm::inverse(glm::dmat4(b));
for (const glm::dvec2& r : region)
for (double z : {-0.5, 0.5}) {
const glm::dvec4 w = invB * glm::dvec4(r, z, 1.0);
const glm::dvec4 q = A * (w / w.w);
const glm::dvec3 n = glm::dvec3(q) / q.w;
bool found = false;
for (const glm::dvec2& s : region)
found = found || (glm::length(glm::dvec2(n) - s) < 1e-5 * (1.0 + glm::length(s)) &&
std::abs(n.z - z) < 1e-5);
if (!found) return false;
}
return true;
};
Mesh current;
const Mesh* src = &doc.mesh;
size_t applied = 0;
std::string lastError;
std::vector<glm::mat4> done;
for (const SymCopy& copy : copies) {
// The copy of the shape: points p with copy^-1(p) inside the original.
glm::mat4 inv(glm::transpose(copy.m));
inv[3] = glm::vec4(copy.pivot - glm::transpose(copy.m) * copy.pivot, 1.0f);
const glm::mat4 view = vp * inv;
if (std::any_of(done.begin(), done.end(), [&](const glm::mat4& d) { return sameCutter(d, view); })) continue;
done.push_back(view);
Mesh next;
if (!cutMesh(*src, view, region, mode, depth, next, lastError, &doc.mesh)) {
// A mirror image beside the Part cuts nothing; any other failure cuts nothing at all, never one
// side only (Discord, dm4nd: with symmetry on, a cut sometimes took one side).
if (lastError.find("misses") != std::string::npos) continue;
if (copies.size() > 1)
lastError += lastError.find("whole Part") != std::string::npos
? " (with its mirror image: turn symmetry off for this cut)"
: " (nothing was cut, on either side)";
return {false, lastError};
}
current = std::move(next);
src = ¤t;
++applied;
}
if (applied == 0) return {true, lastError}; // (every copy missed)
const size_t before = doc.mesh.triangleCount();
doc.replaceMeshUndoable(std::move(current), "Cut");
const char* verb = mode == CutMode::Add ? "Cut Add" : mode == CutMode::In ? "Cut In" : "Cut Away";
return {true, std::string(verb) + ": " + std::to_string(before) + " -> " +
std::to_string(doc.mesh.triangleCount()) + " triangles"};
}});
}
} // namespace sf