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
// Tool > Remesh > Remesh after each stroke (#121): which strokes stretched the surface enough to remesh.
#include "TestHarness.h"
#include "core/CloseHoles.h"
#include "core/Primitives.h"
#include "core/QuickRemesh.h"
#include "core/StarterMeshes.h"
#include "core/Voxel.h"
#include <algorithm>
#include <chrono>
#include <cstdio>
#include <vector>
using namespace sf;
namespace {
// Moves the vertices `moved` to `to(position)`, returning their old positions (as a stroke's undo step holds them).
template <class F> std::vector<glm::vec3> moveVertices(Mesh& mesh, const std::vector<uint32_t>& moved, F to) {
std::vector<glm::vec3> before;
for (uint32_t v : moved) {
before.push_back(mesh.positions[v]);
mesh.positions[v] = to(mesh.positions[v]);
}
return before;
}
double meshVolume(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;
}
// Pieces of a mesh (connected by shared vertices).
size_t pieces(const Mesh& m) {
std::vector<uint32_t> parent(m.vertexCount());
for (uint32_t i = 0; i < parent.size(); ++i) parent[i] = i;
auto find = [&](uint32_t a) {
while (parent[a] != a) a = parent[a] = parent[parent[a]];
return a;
};
for (const glm::uvec3& t : m.triangles) {
parent[find(t.y)] = find(t.x);
parent[find(t.z)] = find(t.x);
}
size_t n = 0;
for (uint32_t i = 0; i < parent.size(); ++i) n += find(i) == i;
return n;
}
// The Stylised Head starter's head (open at the neck), divided once.
Mesh stylisedHead() {
Document d;
std::string error;
const StarterMesh* starter = findStarterMesh("stylised-head");
CHECK(starter && loadStarterMesh(*starter, d, 1, error));
int best = 0;
for (int i = 0; i < d.partCount(); ++i)
if (d.partMesh(i).triangleCount() > d.partMesh(best).triangleCount()) best = i;
return d.partMesh(best);
}
// A Move pull: the vertices within `radius` of `at` follow `delta` with a smooth falloff.
void movePull(Mesh& m, glm::vec3 at, float radius, glm::vec3 delta) {
for (glm::vec3& p : m.positions) {
const float d = glm::distance(p, at) / radius;
if (d < 1.0f) p += delta * (1.0f - d * d) * (1.0f - d * d);
}
m.recomputeAllNormals();
}
} // namespace
TEST(quick_remesh_no_stroke_no_stretch) {
Mesh mesh = makeIcosphere(3);
const StrokeStretch s = strokeStretch(mesh, {}, {});
CHECK(s.edges == 0);
CHECK(!stretchWantsRemesh(s));
}
TEST(quick_remesh_gentle_stroke_keeps_the_mesh) {
// Every vertex 20% further out: every edge 1.2 times as long, under the 1.6 threshold.
Mesh mesh = makeIcosphere(3);
std::vector<uint32_t> all;
for (uint32_t v = 0; v < mesh.positions.size(); ++v) all.push_back(v);
const std::vector<glm::vec3> before = moveVertices(mesh, all, [](glm::vec3 p) { return p * 1.2f; });
const StrokeStretch s = strokeStretch(mesh, all, before);
CHECK(s.edges > 0);
CHECK(s.stretched == 0);
CHECK(s.worst > 1.15f && s.worst < 1.25f);
CHECK(!stretchWantsRemesh(s));
}
TEST(quick_remesh_pulled_vertex_remeshes) {
// One vertex pulled far out (a Move or Snake Hook pull): its whole ring of edges stretched. (Vertex 20 has six
// neighbours; the twelve first ones, the icosahedron's corners, have five, one short of kStretchedEdges.)
Mesh mesh = makeIcosphere(3);
CHECK(mesh.neighbors(20).size() == 6);
const std::vector<uint32_t> moved{20};
const std::vector<glm::vec3> before = moveVertices(mesh, moved, [](glm::vec3 p) { return p * 3.0f; });
const StrokeStretch s = strokeStretch(mesh, moved, before);
CHECK(s.edges == mesh.neighbors(20).size());
CHECK(s.stretched == s.edges);
CHECK(s.worst > 5.0f);
CHECK(stretchWantsRemesh(s));
}
TEST(quick_remesh_edges_between_moved_vertices_count_once) {
// Everything scaled 3x: each edge is counted once (both ends moved) and every one is stretched.
Mesh mesh = makeIcosphere(2);
std::vector<uint32_t> all;
size_t ends = 0;
for (uint32_t v = 0; v < mesh.positions.size(); ++v) {
all.push_back(v);
ends += mesh.neighbors(v).size();
}
const std::vector<glm::vec3> before = moveVertices(mesh, all, [](glm::vec3 p) { return p * 3.0f; });
const StrokeStretch s = strokeStretch(mesh, all, before);
CHECK(s.edges == ends / 2);
CHECK(s.stretched == s.edges);
CHECK(stretchWantsRemesh(s));
}
TEST(quick_remesh_vertices_out_of_range_are_skipped) {
Mesh mesh = makeIcosphere(1);
const std::vector<uint32_t> moved{uint32_t(mesh.positions.size()) + 5};
const std::vector<glm::vec3> before{glm::vec3(0.0f)};
CHECK(strokeStretch(mesh, moved, before).edges == 0);
}
// Launch clips (11-05): Quick Remesh and Voxel Remesh of the Stylised Head (open at the neck) after a Move pull near
// the neck gave a thin shell full of holes (the outside flooded in through the neck). Now the neck is capped first:
// one closed piece about as big as the head (it was 6-17 % of its volume in 3-17 pieces).
TEST(voxel_remesh_open_starter_head_stays_solid) {
Mesh head = stylisedHead();
CHECK(!boundaryLoops(head).empty()); // (open at the neck)
const AABB box = head.bounds();
const float size = glm::length(box.extent());
// Near the neck: the lowest tenth, at the front; pulled forward and down.
glm::vec3 neck(box.center().x, box.min.y + 0.1f * box.extent().y, box.max.z);
float bestD = 1e30f;
glm::vec3 at = neck;
for (const glm::vec3& p : head.positions)
if (const float d = glm::distance(p, neck); d < bestD) bestD = d, at = p;
for (int pulled = 0; pulled < 2; ++pulled) {
if (pulled) movePull(head, at, 0.15f * size, glm::vec3(0.0f, -0.05f, 0.12f) * size);
Mesh closed = head;
CloseHolesOptions o;
o.refine = false;
CloseHolesStats stats;
std::string err;
CHECK(closeHoles(closed, o, stats, err));
const double expected = std::abs(meshVolume(closed));
for (int res : {123, 64, 200}) {
const auto t0 = std::chrono::steady_clock::now();
Mesh r = voxelRemesh(head, res, &err);
const double ms = std::chrono::duration<double, std::milli>(std::chrono::steady_clock::now() - t0).count();
std::printf(" stylised head%s res %d: %zu triangles, volume %.3f of the capped head, %zu piece(s), %.0f ms\n",
pulled ? " pulled" : "", res, r.triangleCount(), meshVolume(r) / expected, pieces(r), ms);
CHECK(r.triangleCount() > 1000);
CHECK(boundaryLoops(r).empty());
CHECK(pieces(r) == 1);
CHECK(std::abs(meshVolume(r) / expected - 1.0) < 0.1);
}
}
}
// A mesh that can't be made solid keeps the original: an empty result and a reason, never a holed shell. A sphere
// with its top cut off and a fin on one edge of the opening: that edge has two triangles, so the border is no loop
// Fill Holes can cap, and the outside floods in.
TEST(voxel_remesh_uncappable_open_mesh_says_why) {
Mesh bowl = makeIcosphere(4);
std::vector<glm::uvec3> kept;
for (const glm::uvec3& t : bowl.triangles)
if ((bowl.positions[t.x].y + bowl.positions[t.y].y + bowl.positions[t.z].y) / 3.0f <= 0.6f) kept.push_back(t);
bowl.triangles = kept;
bowl.rebuildTopology();
std::string err;
Mesh r = voxelRemesh(bowl, 64, &err);
CHECK(r.triangleCount() > 1000 && err.empty()); // (capped: solid)
CHECK(boundaryLoops(r).empty() && pieces(r) == 1);
CHECK(meshVolume(r) > 3.5); // (the unit sphere less a thin cap: 4.19 less about 0.44)
const std::vector<std::vector<uint32_t>> loops = boundaryLoops(bowl);
CHECK(loops.size() == 1);
Mesh fin = bowl;
const uint32_t a = loops[0][0], b = loops[0][1];
fin.positions.push_back((fin.positions[a] + fin.positions[b]) * 0.5f + glm::vec3(0.0f, 0.3f, 0.0f));
fin.triangles.push_back(glm::uvec3(a, b, uint32_t(fin.positions.size() - 1))); // (a -> b twice)
fin.rebuildTopology();
CHECK(boundaryLoops(fin).empty()); // (nothing Fill Holes could cap)
err.clear();
CHECK(voxelRemesh(fin, 64, &err).triangleCount() == 0);
CHECK(err.find("open borders") != std::string::npos);
CHECK(err.find("unchanged") != std::string::npos);
}