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 (#101, #91): every shape and mode on a sphere, a low-poly cube and a two-Part scene; watertight results,
// attributes, symmetry, perspective views, open meshes and undo. Also Lasso Mask "Front faces only" (#91.3).
#include "TestHarness.h"
#include "core/Commands.h"
#include "core/Cut.h"
#include "core/Masking.h"
#include "core/Primitives.h"
#include "core/ScreenSelect.h"
#include <glm/gtc/matrix_transform.hpp>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace sf;
namespace {
const CommandRegistry& registry() {
static CommandRegistry r;
return r;
}
double volume(const Mesh& m) {
double v = 0.0;
for (const glm::uvec3& t : m.triangles)
v += glm::dot(glm::dvec3(m.positions[t.x]), glm::cross(glm::dvec3(m.positions[t.y]), glm::dvec3(m.positions[t.z])));
return v / 6.0;
}
CommandResult cut(Document& d, const std::string& shape, const std::string& points, const std::string& mode,
Args extra = {}) {
extra["shape"] = shape;
extra["points"] = points;
extra["mode"] = mode;
return registry().execute(d, "cut", extra);
}
std::string matrixString(const glm::mat4& m) {
std::string s;
char buf[32];
for (int i = 0; i < 16; ++i) {
std::snprintf(buf, sizeof buf, "%s%.9g", i ? " " : "", double(m[i / 4][i % 4]));
s += buf;
}
return s;
}
// Vertices inside an axis box of x, y (the front view's NDC is world x, y for a unit sphere) and above z.
size_t countIn(const Mesh& m, float x0, float x1, float y0, float y1, float zAbove = -1e9f) {
size_t n = 0;
for (const glm::vec3& p : m.positions)
if (p.x > x0 && p.x < x1 && p.y > y0 && p.y < y1 && p.z > zAbove) ++n;
return n;
}
const double kSphere = 4.0 / 3.0 * 3.14159265358979;
} // namespace
TEST(cut_command_registered) {
CHECK(registry().find("cut") != nullptr);
CHECK(registry().toolSchemaJson().find("\"cut\"") != std::string::npos);
CutShape s;
CutMode m;
CHECK(parseCutShape("polyline", s) && s == CutShape::Polyline);
CHECK(parseCutMode("add", m) && m == CutMode::Add);
CHECK(!parseCutMode("trim", m));
}
TEST(cut_line_away_halves_sphere) {
Document d = makeDoc(makeIcosphere(4));
CHECK(isWatertight(d.mesh));
const double v0 = volume(d.mesh);
// A vertical line upwards: the left (-x) half goes, a flat cap closes the right half.
const CommandResult r = cut(d, "line", "0.013 -2 0.013 2", "away");
CHECK(r.ok);
CHECK(isWatertight(d.mesh));
size_t left = 0, onCap = 0;
for (const glm::vec3& p : d.mesh.positions) {
if (p.x < 0.013f - 1e-4f) ++left;
if (std::abs(p.x - 0.013f) < 1e-4f) ++onCap;
}
CHECK(left == 0);
CHECK(onCap > 20);
const double v1 = volume(d.mesh);
CHECK(v1 > 0.4 * v0 && v1 < 0.5 * v0); // a bit under half: the line is right of centre
// The cap is a face group of its own.
CHECK(d.mesh.hasFaceGroups());
// Flip keeps the other half.
Document e = makeDoc(makeIcosphere(4));
CHECK(cut(e, "line", "0.013 -2 0.013 2", "away", {{"flip", true}}).ok);
CHECK(isWatertight(e.mesh));
for (const glm::vec3& p : e.mesh.positions) CHECK(p.x < 0.013f + 1e-4f);
CHECK(std::abs(volume(e.mesh) + v1 - v0) < 0.02 * v0);
// Undo brings the sphere back.
CHECK(registry().execute(d, "undo").ok);
CHECK(std::abs(volume(d.mesh) - v0) < 1e-6);
}
TEST(cut_every_shape_away_through_sphere) {
struct Case {
const char* shape;
const char* points;
bool closed;
} cases[] = {
{"rect", "-0.31 -0.29 0.33 0.27", false},
{"lasso", "-0.5 -0.47 0.52 -0.45 0.03 0.61", false},
{"polyline", "-0.5 -0.47 0.52 -0.45 0.03 0.61", true},
};
for (const Case& c : cases) {
Document d = makeDoc(makeIcosphere(4));
const double v0 = volume(d.mesh);
const CommandResult r = cut(d, c.shape, c.points, "away", {{"closed", c.closed}});
CHECK(r.ok);
CHECK(isWatertight(d.mesh)); // a tunnel through the sphere
CHECK(volume(d.mesh) < 0.9 * v0);
CHECK(countIn(d.mesh, -0.1f, 0.1f, -0.2f, 0.1f) == 0);
}
// Open polyline: a bent line, cutting the top-left away.
Document d = makeDoc(makeIcosphere(4));
CHECK(cut(d, "polyline", "-2 0.21 0.02 0.21 0.53 -2", "away").ok);
CHECK(isWatertight(d.mesh));
CHECK(countIn(d.mesh, -2.0f, -0.05f, 0.25f, 2.0f) == 0);
CHECK(countIn(d.mesh, -2.0f, -0.05f, -2.0f, 0.15f) > 0);
}
TEST(cut_in_and_add_on_sphere) {
// In: a flat-bottomed pocket 0.4 deep (depth 0.2 of the size 2) in the front.
Document d = makeDoc(makeIcosphere(4));
const double v0 = volume(d.mesh);
CHECK(cut(d, "rect", "-0.31 -0.29 0.33 0.27", "in", {{"depth", 0.2}}).ok);
CHECK(isWatertight(d.mesh));
CHECK(volume(d.mesh) < v0 && volume(d.mesh) > 0.8 * v0);
float bottom = 1e9f;
for (const glm::vec3& p : d.mesh.positions)
if (std::abs(p.x) < 0.4f && std::abs(p.y) < 0.4f && p.z > 0.3f) bottom = std::min(bottom, p.z); // floor corners
CHECK(bottom > 0.5f && bottom < 0.62f); // the pocket floor: front (~0.95) minus 0.4
CHECK(countIn(d.mesh, -0.2f, 0.2f, -0.2f, 0.2f, bottom + 0.01f) == 0);
CHECK(countIn(d.mesh, -0.2f, 0.2f, -0.2f, 0.2f) > 0); // the back of the sphere is still there
// Add: the rectangle extruded 0.4 towards the viewer, anchored in the sphere.
Document a = makeDoc(makeIcosphere(4));
CHECK(cut(a, "rect", "-0.31 -0.29 0.33 0.27", "add", {{"depth", 0.2}}).ok);
CHECK(isWatertight(a.mesh));
CHECK(volume(a.mesh) > v0 * 1.02);
CHECK(a.mesh.bounds().max.z > 1.3f);
for (const char* shape : {"lasso", "polyline"}) {
Document b = makeDoc(makeIcosphere(4));
CHECK(cut(b, shape, "-0.5 -0.47 0.52 -0.45 0.03 0.61", "add", {{"depth", 0.1}, {"closed", true}}).ok);
CHECK(isWatertight(b.mesh));
CHECK(volume(b.mesh) > v0);
Document c = makeDoc(makeIcosphere(4));
CHECK(cut(c, shape, "-0.5 -0.47 0.52 -0.45 0.03 0.61", "in", {{"depth", 0.1}, {"closed", true}}).ok);
CHECK(isWatertight(c.mesh));
CHECK(volume(c.mesh) < v0);
}
// Line In: a step cut off the front.
Document l = makeDoc(makeIcosphere(4));
CHECK(cut(l, "line", "0.013 -2 0.013 2", "in", {{"depth", 0.3}}).ok);
CHECK(isWatertight(l.mesh));
CHECK(volume(l.mesh) < v0);
}
TEST(cut_low_poly_cube_hole_inside_one_triangle) {
// A small lasso inside one face of a 12-triangle cube: the cut's outline sits inside a triangle (a hole to bridge).
Document d = makeDoc(makeCube(1));
const size_t t0 = d.mesh.triangleCount();
CHECK(cut(d, "lasso", "-0.21 -0.18 0.23 -0.2 0.27 0.22 -0.19 0.24", "in", {{"depth", 0.25}}).ok);
CHECK(isWatertight(d.mesh));
CHECK(d.mesh.triangleCount() > t0);
CHECK(std::abs(volume(d.mesh) - (8.0 - 0.44 * 0.43 * 0.5)) < 0.1);
Document a = makeDoc(makeCube(1));
CHECK(cut(a, "rect", "-0.21 -0.18 0.23 0.24", "add", {{"depth", 0.25}}).ok);
CHECK(isWatertight(a.mesh));
CHECK(volume(a.mesh) > 8.0);
Document w = makeDoc(makeCube(1));
CHECK(cut(w, "rect", "-0.21 -0.18 0.23 0.24", "away").ok);
CHECK(isWatertight(w.mesh));
CHECK(std::abs(volume(w.mesh) - (8.0 - 2.0 * 0.44 * 0.42)) < 0.05);
}
TEST(cut_perspective_view_and_symmetry) {
Document d = makeDoc(makeIcosphere(4));
const glm::mat4 vp = glm::perspective(glm::radians(40.0f), 1.3f, 0.1f, 100.0f) *
glm::lookAt(glm::vec3(0.7f, 0.9f, 4.0f), glm::vec3(0.0f), glm::vec3(0, 1, 0));
const double v0 = volume(d.mesh);
CHECK(cut(d, "lasso", "-0.1 -0.1 0.12 -0.08 0.02 0.15", "away", {{"view_proj", matrixString(vp)}}).ok);
CHECK(isWatertight(d.mesh));
CHECK(volume(d.mesh) < v0);
CHECK(cut(d, "rect", "-0.05 -0.4 0.05 0.4", "add", {{"view_proj", matrixString(vp)}, {"depth", 0.1}}).ok);
CHECK(isWatertight(d.mesh));
// X symmetry: a rectangle on the right also cuts its mirror image on the left.
Document s = makeDoc(makeIcosphere(4));
CHECK(cut(s, "rect", "0.31 -0.19 0.61 0.21", "away", {{"symmetry", std::string("x")}}).ok);
CHECK(isWatertight(s.mesh));
CHECK(countIn(s.mesh, 0.36f, 0.56f, -0.14f, 0.16f) == 0);
CHECK(countIn(s.mesh, -0.56f, -0.36f, -0.14f, 0.16f) == 0);
CHECK(countIn(s.mesh, -0.2f, 0.2f, -0.14f, 0.16f) > 0);
}
TEST(cut_two_part_scene_cuts_active_part_only) {
Document d = makeDoc(makeIcosphere(4));
CHECK(registry().execute(d, "part_append", {{"type", std::string("sphere")}}).ok);
CHECK(d.parts.size() == 2 && d.activePart == 1);
const Mesh other = d.partMesh(0);
const double v0 = volume(d.mesh);
const AABB b = d.mesh.bounds();
// The default view frames the active Part: a line through its middle.
CHECK(cut(d, "line", "0.013 -2 0.013 2", "away").ok);
CHECK(isWatertight(d.mesh));
CHECK(volume(d.mesh) < 0.6 * v0);
for (const glm::vec3& p : d.mesh.positions) CHECK(p.x > b.center().x - 0.01f * b.extent().x);
// The other Part is untouched.
CHECK(d.partMesh(0).triangleCount() == other.triangleCount());
CHECK(d.partMesh(0).positions == other.positions);
// Undo and redo.
CHECK(registry().execute(d, "undo").ok);
CHECK(std::abs(volume(d.mesh) - v0) < 1e-6);
CHECK(registry().execute(d, "redo").ok);
CHECK(volume(d.mesh) < 0.6 * v0);
// Every mode on the other Part too.
CHECK(registry().execute(d, "part_select", {{"index", 0.0}}).ok);
for (const char* mode : {"away", "in", "add"}) {
const size_t before = d.undo.undoCount();
CHECK(cut(d, "rect", "-0.31 -0.29 0.33 0.27", mode, {{"depth", 0.15}}).ok);
CHECK(isWatertight(d.mesh));
CHECK(d.undo.undoCount() == before + 1);
}
}
TEST(cut_attributes_misses_and_open_meshes) {
Document d = makeDoc(makeIcosphere(4));
d.mesh.ensureMask(1.0f);
d.mesh.ensureColors(glm::vec3(0.2f, 0.4f, 0.6f));
CHECK(cut(d, "line", "0.013 -2 0.013 2", "away").ok);
size_t masked = 0;
for (float m : d.mesh.mask) masked += m > 0.99f;
CHECK(masked > d.mesh.vertexCount() / 2); // the kept surface keeps its mask; only the cap's inner corners are free
for (const glm::vec3& c : d.mesh.colors) CHECK(glm::length(c - glm::vec3(0.2f, 0.4f, 0.6f)) < 1e-3f);
// A shape off the Part changes nothing and adds no undo step.
Document m = makeDoc(makeIcosphere(3));
const size_t steps = m.undo.undoCount();
const CommandResult miss = cut(m, "rect", "3 3 4 4", "away");
CHECK(miss.ok && miss.message.find("misses") != std::string::npos);
CHECK(m.undo.undoCount() == steps);
// Covering all of it is refused.
CHECK(!cut(m, "rect", "-5 -5 5 5", "away").ok);
// Bad arguments.
CHECK(!cut(m, "line", "0 0", "away").ok);
CHECK(!cut(m, "lasso", "0 0 1 1", "away").ok);
CHECK(!cut(m, "lasso", "0 0 1 1 0.5 0.5", "sideways").ok);
// An open plane is trimmed without a cap; Add needs a closed Part.
Document p = makeDoc(makePlane(16));
const size_t t0 = p.mesh.triangleCount();
const glm::mat4 top = glm::ortho(-1.0f, 1.0f, -1.0f, 1.0f, 0.1f, 10.0f) *
glm::lookAt(glm::vec3(0, 5, 0), glm::vec3(0.0f), glm::vec3(0, 0, -1));
const AABB pb = p.mesh.bounds();
const bool flat = pb.extent().y < 1e-4f; // makePlane lies in XZ
const std::string view = flat ? matrixString(top) : std::string();
Args a{{"view_proj", view}};
if (view.empty()) a.erase("view_proj");
CHECK(cut(p, "line", "0.013 -2 0.013 2", "away", a).ok);
CHECK(p.mesh.triangleCount() < t0);
CHECK(!isWatertight(p.mesh));
CHECK(!cut(p, "rect", "-0.3 -0.3 0.3 0.3", "add", a).ok);
}
TEST(mask_lasso_front_faces_only) {
Document d = makeDoc(makeIcosphere(3));
// The whole sphere seen from the front: only the half facing the viewer (+Z) is masked.
CHECK(registry().execute(d, "mask_rect", {{"x0", -2.0}, {"y0", -2.0}, {"x1", 2.0}, {"y1", 2.0}, {"front_faces_only", true}}).ok);
size_t wrong = 0, masked = 0;
for (uint32_t v = 0; v < d.mesh.vertexCount(); ++v) {
const float z = d.mesh.normals[v].z;
const bool m = d.mesh.mask[v] > 0.5f;
masked += m;
if (std::abs(z) > 0.05f && m != (z > 0.0f)) ++wrong;
}
CHECK(wrong == 0);
CHECK(masked > 0 && masked < d.mesh.vertexCount());
CHECK(registry().execute(d, "mask_clear").ok);
CHECK(registry().execute(d, "mask_lasso", {{"points", std::string("-2 -2 2 -2 0 2")}, {"front_faces_only", true}}).ok);
for (uint32_t v = 0; v < d.mesh.vertexCount(); ++v)
if (d.mesh.normals[v].z < -0.05f) CHECK(d.mesh.mask[v] == 0.0f);
// Without the option the back is masked too.
CHECK(registry().execute(d, "mask_lasso", {{"points", std::string("-2 -2 2 -2 0 2")}}).ok);
size_t back = 0;
for (uint32_t v = 0; v < d.mesh.vertexCount(); ++v) back += d.mesh.normals[v].z < -0.5f && d.mesh.mask[v] > 0.5f;
CHECK(back > 0);
}
TEST(cut_clip_presses_flat_without_removing) {
// #102: a line clips the shaded side flat onto the line; nothing is removed, the depth (z) is kept.
const Mesh sphere = makeIcosphere(4);
Document d = makeDoc(sphere);
CommandResult r = cut(d, "line", "0.5 -2 0.5 2", "clip", {{"flip", true}}); // the right side (x > 0.5)
CHECK(r.ok);
CHECK(r.message.find("Clip:") == 0);
CHECK(d.mesh.vertexCount() == sphere.vertexCount() && d.mesh.triangles == sphere.triangles);
float maxX = -1.0f;
for (size_t v = 0; v < sphere.vertexCount(); ++v) {
maxX = std::max(maxX, d.mesh.positions[v].x);
CHECK(std::abs(d.mesh.positions[v].z - sphere.positions[v].z) < 1e-4f);
if (sphere.positions[v].x < 0.49f) CHECK(d.mesh.positions[v] == sphere.positions[v]);
}
CHECK(maxX < 0.5f + 1e-3f && maxX > 0.5f - 1e-3f);
CHECK(isWatertight(d.mesh));
CHECK(registry().execute(d, "undo").ok);
CHECK(d.mesh.positions == sphere.positions);
// A rectangle presses everything outside it onto its outline.
r = cut(d, "rect", "-0.4 -0.3 0.4 0.3", "clip");
CHECK(r.ok);
for (const glm::vec3& p : d.mesh.positions) CHECK(std::abs(p.x) < 0.401f && std::abs(p.y) < 0.301f);
CHECK(registry().execute(d, "undo").ok);
// The mask holds vertices back; a fully masked Part doesn't move.
d.mesh.ensureMask(1.0f);
r = cut(d, "rect", "-0.4 -0.3 0.4 0.3", "clip");
CHECK(r.ok && r.message.find("misses") != std::string::npos);
CHECK(d.mesh.positions == sphere.positions);
// Symmetry X: a line on the right clips the left too.
Document s = makeDoc(sphere);
CHECK(cut(s, "line", "0.5 -2 0.5 2", "clip", {{"flip", true}, {"symmetry", std::string("x")}}).ok);
float minX = 1.0f;
for (const glm::vec3& p : s.mesh.positions) minX = std::min(minX, p.x);
CHECK(minX > -0.501f);
}
namespace {
// Points of a grid that are inside the mesh while their X mirror image is not (rays along z, even-odd): 0 for a
// mesh symmetric about x = 0. Also counts rays whose crossings are odd (a hole in the surface).
std::pair<size_t, size_t> mirrorMismatch(const Mesh& m, int n = 48) {
auto insideColumn = [&](double x, double y, std::vector<double>& zs) {
zs.clear();
for (const glm::uvec3& t : m.triangles) {
const glm::dvec3 a(m.positions[t.x]), b(m.positions[t.y]), c(m.positions[t.z]);
const double d = (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
if (d == 0.0) continue;
const double u = ((x - a.x) * (c.y - a.y) - (c.x - a.x) * (y - a.y)) / d;
const double v = ((b.x - a.x) * (y - a.y) - (x - a.x) * (b.y - a.y)) / d;
if (u < 0 || v < 0 || u + v > 1) continue;
zs.push_back(a.z + u * (b.z - a.z) + v * (c.z - a.z));
}
std::sort(zs.begin(), zs.end());
};
size_t bad = 0, odd = 0;
std::vector<double> za, zb;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) {
const double x = -1.3 + 2.6 * (i + 0.5137) / n, y = -1.3 + 2.6 * (j + 0.4719) / n;
insideColumn(x, y, za);
insideColumn(-x, y, zb);
odd += (za.size() % 2) + (zb.size() % 2);
for (int k = 0; k < n; ++k) {
const double z = -1.3 + 2.6 * (k + 0.5) / n;
auto in = [z](const std::vector<double>& zs) {
return (std::upper_bound(zs.begin(), zs.end(), z) - zs.begin()) % 2 == 1;
};
bad += in(za) != in(zb);
}
}
return {bad, odd};
}
} // namespace
// Discord (dm4nd): with symmetry on, a cut sometimes took one side only, and a cap sometimes failed to close. A mirror
// image that overlaps the shape (a rectangle across the middle, a centred one seen at an angle) cut into the pocket
// the first copy had made: In and Add measured their depth from there, and in the axis views the copies' walls fell
// on each other, leaving zero-area triangles that cracked the next cut, which then dropped the mirror image silently.
TEST(cut_symmetry_overlapping_mirror_images) {
const glm::mat4 front = glm::ortho(-1.5f, 1.5f, -1.5f, 1.5f, 0.1f, 100.0f) *
glm::lookAt(glm::vec3(0, 0, 4), glm::vec3(0), glm::vec3(0, 1, 0));
const glm::mat4 angled = glm::perspective(glm::radians(40.0f), 1.3f, 0.1f, 100.0f) *
glm::lookAt(glm::vec3(0.7f, 0.9f, 4.0f), glm::vec3(0.0f), glm::vec3(0, 1, 0));
struct Shape {
const char* shape;
const char* points;
bool closed;
};
const Shape shapes[] = {{"rect", "-0.1 -0.2 0.4 0.2", false},
{"lasso", "-0.1 -0.2 0.4 -0.15 0.35 0.25 -0.05 0.2", true},
{"rect", "-0.2 -0.2 0.2 0.2", false}};
const glm::mat4 views[] = {front, angled};
for (int v = 0; v < 2; ++v)
for (const Shape& sh : shapes)
for (const char* mode : {"away", "in", "add", "clip"})
for (bool twice : {false, true}) {
Document d = makeDoc(makeIcosphere(4));
Args args = {{"view_proj", matrixString(views[v])}, {"closed", sh.closed}, {"depth", 0.1},
{"symmetry", std::string("x")}};
CHECK(cut(d, sh.shape, sh.points, mode, args).ok);
if (twice) { // a second cut across the first one's caps, from the other view
args["view_proj"] = matrixString(views[1 - v]);
CHECK(cut(d, "rect", "-0.15 -0.3 0.35 0.1", mode, args).ok);
}
const auto [mismatch, open] = mirrorMismatch(d.mesh, 24);
CHECK(isWatertight(d.mesh));
CHECK(open == 0);
CHECK(mismatch <= 30); // (of 24^3 samples: the outline's own jitter)
}
}
// A mirror image that can't be cut cuts nothing at all, never one side only.
TEST(cut_symmetry_all_or_nothing) {
Document d = makeDoc(makeIcosphere(4));
const size_t before = d.mesh.triangleCount();
// Upwards through the middle cuts the left half; its mirror image would take the right half: the whole Part.
const CommandResult r = cut(d, "line", "0.013 -2 0.013 2", "away", {{"symmetry", std::string("x")}});
CHECK(!r.ok);
CHECK(r.message.find("symmetry") != std::string::npos);
CHECK(d.mesh.triangleCount() == before);
}