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
#include "core/MeshCheck.h"
#include "core/CloseHoles.h"
#include "core/Commands.h"
#include "core/FaceGroups.h"
#include "core/Parallel.h"
#include <algorithm>
#include <cmath>
#include <mutex>
#include <numeric>
#include <sstream>
namespace sf {
namespace {
constexpr uint32_t kNone = ~0u;
bool degenerate(const glm::uvec3& t) { return t.x == t.y || t.y == t.z || t.x == t.z; }
// Does triangle t run a -> b (rather than b -> a)? (t has both.)
bool runs(const glm::uvec3& t, uint32_t a, uint32_t b) {
return (t.x == a && t.y == b) || (t.y == a && t.z == b) || (t.z == a && t.x == b);
}
bool has(const glm::uvec3& t, uint32_t v) { return t.x == v || t.y == v || t.z == v; }
// The non-degenerate triangles around `a` that also use `b`, ascending, into `out`.
void edgeTriangles(const Mesh& mesh, uint32_t a, uint32_t b, std::vector<uint32_t>& out) {
out.clear();
for (uint32_t t : mesh.vertexTriangles(a))
if (has(mesh.triangles[t], b) && !degenerate(mesh.triangles[t])) out.push_back(t);
std::sort(out.begin(), out.end());
}
// Zero area: three distinct points (all but) in one line, the triangle's height under a millionth of its longest edge.
bool zeroArea(const Mesh& mesh, const glm::uvec3& t) {
const glm::vec3 a = mesh.positions[t.x], b = mesh.positions[t.y], c = mesh.positions[t.z];
const float longest = std::max({glm::dot(b - a, b - a), glm::dot(c - b, c - b), glm::dot(a - c, a - c)});
const float cross = glm::length(glm::cross(b - a, c - a));
return cross <= 1e-6f * longest;
}
// The triangle earlier than t on the same three points, either winding.
bool duplicateOfEarlier(const Mesh& mesh, uint32_t t) {
const glm::uvec3 a = mesh.triangles[t];
for (uint32_t u : mesh.vertexTriangles(a.x)) {
if (u >= t) continue;
const glm::uvec3 b = mesh.triangles[u];
if (has(b, a.y) && has(b, a.z) && !degenerate(b)) return true;
}
return false;
}
struct UnionFind {
std::vector<uint32_t> parent;
explicit UnionFind(size_t n) : parent(n) { std::iota(parent.begin(), parent.end(), 0u); }
uint32_t find(uint32_t v) {
while (parent[v] != v) v = parent[v] = parent[parent[v]];
return v;
}
void unite(uint32_t a, uint32_t b) { // the lower index is the root
a = find(a), b = find(b);
if (a != b) parent[std::max(a, b)] = std::min(a, b);
}
};
// Which triangles to flip so each piece is wound one way (its majority), and closed pieces face outward.
std::vector<uint8_t> flipsNeeded(const Mesh& mesh, size_t& count) {
const size_t nt = mesh.triangleCount();
std::vector<uint8_t> flip(nt, 0), seen(nt, 0);
std::vector<uint32_t> piece, around;
const glm::vec3 origin = mesh.bounds().valid() ? mesh.bounds().center() : glm::vec3(0.0f);
count = 0;
for (uint32_t seed = 0; seed < nt; ++seed) {
if (seen[seed] || degenerate(mesh.triangles[seed]) || duplicateOfEarlier(mesh, seed)) continue;
piece.assign(1, seed);
seen[seed] = 1;
bool closed = true;
for (size_t i = 0; i < piece.size(); ++i) {
const uint32_t t = piece[i];
const glm::uvec3 tri = mesh.triangles[t];
for (int k = 0; k < 3; ++k) {
const uint32_t a = tri[k], b = tri[(k + 1) % 3];
edgeTriangles(mesh, a, b, around);
if (around.size() != 2) { // an open or non-manifold edge: no neighbour to agree with
closed = false;
continue;
}
const uint32_t u = around[0] == t ? around[1] : around[0];
if (seen[u]) continue;
seen[u] = 1;
// Consistent neighbours run the shared edge the other way: the same way means one of them is flipped.
const bool sameWay = runs(mesh.triangles[u], a, b);
flip[u] = uint8_t(flip[t] ^ (sameWay ? 1 : 0));
piece.push_back(u);
}
}
size_t ones = 0;
for (uint32_t t : piece) ones += flip[t];
bool invert = ones * 2 > piece.size();
if (closed) { // a closed piece wound inside out (negative volume) is turned the right way out as a whole
double volume = 0.0;
for (uint32_t t : piece) {
const glm::uvec3 tri = mesh.triangles[t];
const glm::dvec3 a(mesh.positions[tri.x] - origin), b(mesh.positions[tri.y] - origin),
c(mesh.positions[tri.z] - origin);
const double v = glm::dot(a, glm::cross(b, c));
volume += (flip[t] != 0) != invert ? -v : v;
}
if (volume < 0.0) invert = !invert;
}
for (uint32_t t : piece) {
if (invert) flip[t] ^= 1;
count += flip[t];
}
}
return flip;
}
// The first two triangles of a non-manifold edge stay joined across it: the first and the first one after it wound
// the other way (a consistent pair), else the second.
std::pair<uint32_t, uint32_t> keptPair(const Mesh& mesh, uint32_t a, uint32_t b, const std::vector<uint32_t>& around) {
const bool first = runs(mesh.triangles[around[0]], a, b);
for (size_t i = 1; i < around.size(); ++i)
if (runs(mesh.triangles[around[i]], a, b) != first) return {around[0], around[i]};
return {around[0], around[1]};
}
Mesh withoutTriangles(const Mesh& mesh, const std::vector<uint8_t>& drop) {
std::vector<uint8_t> keep(drop.size());
for (size_t t = 0; t < drop.size(); ++t) keep[t] = !drop[t];
return extractTriangles(mesh, keep);
}
// Every triangle's corners through `target`; those that collapse are dropped.
Mesh remapped(const Mesh& mesh, const std::vector<uint32_t>& target) {
std::vector<glm::uvec3> corners(mesh.triangles);
std::vector<uint8_t> keep(corners.size());
for (size_t t = 0; t < corners.size(); ++t) {
for (int k = 0; k < 3; ++k) corners[t][k] = target[corners[t][k]];
keep[t] = !degenerate(corners[t]);
}
TriangleRebuild how;
how.corners = &corners;
return rebuildTriangles(mesh, keep, how);
}
uint64_t mix(uint64_t x) { // splitmix64's finaliser
x ^= x >> 30;
x *= 0xbf58476d1ce4e5b9ull;
x ^= x >> 27;
x *= 0x94d049bb133111ebull;
return x ^ (x >> 31);
}
} // namespace
std::vector<uint32_t> weldTargets(const Mesh& mesh, float distance, size_t* merged) {
const size_t nv = mesh.vertexCount();
std::vector<uint32_t> target(nv);
std::iota(target.begin(), target.end(), 0u);
size_t n = 0;
const AABB box = mesh.bounds();
if (nv > 1 && box.valid()) {
// A grid of cells at least twice `distance` wide holding the kept points: a point's matches are in its cell
// and, along each axis, at most the one neighbour on the side it is near (8 cells at most). Kept points are
// over `distance` apart, so a cell holds only a few of them, whatever the distance.
const float d = std::max(0.0f, std::isfinite(distance) ? distance : 0.0f);
const float cell = std::max({2.0f * d, glm::length(box.extent()) * 1e-6f, 1e-30f});
constexpr int kBits = 21, kMax = (1 << kBits) - 1;
auto coord = [&](float v, float lo) { return std::clamp(int((v - lo) / cell), 0, kMax); };
auto key = [](int x, int y, int z) { return (uint64_t(x) << (2 * kBits)) | (uint64_t(y) << kBits) | uint64_t(z); };
size_t cap = 16;
while (cap < nv * 2) cap <<= 1;
std::vector<uint64_t> keys(cap, ~0ull);
std::vector<uint32_t> head(cap, kNone), next(nv, kNone);
auto slot = [&](uint64_t k) {
size_t i = mix(k) & (cap - 1);
while (keys[i] != ~0ull && keys[i] != k) i = (i + 1) & (cap - 1);
return i;
};
const float d2 = d * d;
for (uint32_t v = 0; v < nv; ++v) {
const glm::vec3 p = mesh.positions[v];
if (!std::isfinite(p.x) || !std::isfinite(p.y) || !std::isfinite(p.z)) continue; // stays, never matched
const int cx = coord(p.x, box.min.x), cy = coord(p.y, box.min.y), cz = coord(p.z, box.min.z);
// The neighbour cell each axis needs: -1 / +1 when p is within d of that face, else none (0).
auto side = [&](float v, float lo, int c) {
const float local = v - lo - float(c) * cell;
return local <= d ? -1 : local >= cell - d ? 1 : 0;
};
const int sx = side(p.x, box.min.x, cx), sy = side(p.y, box.min.y, cy), sz = side(p.z, box.min.z, cz);
uint32_t best = kNone;
float bestD = d2;
for (int dx = std::min(0, sx); dx <= std::max(0, sx); ++dx)
for (int dy = std::min(0, sy); dy <= std::max(0, sy); ++dy)
for (int dz = std::min(0, sz); dz <= std::max(0, sz); ++dz) {
const int x = cx + dx, y = cy + dy, z = cz + dz;
if (x < 0 || y < 0 || z < 0 || x > kMax || y > kMax || z > kMax) continue;
const size_t i = slot(key(x, y, z));
for (uint32_t u = keys[i] == ~0ull ? kNone : head[i]; u != kNone; u = next[u]) {
const glm::vec3 e = mesh.positions[u] - p;
const float dd = glm::dot(e, e);
if (dd < bestD || (dd == bestD && (best == kNone || u < best))) {
best = u;
bestD = dd;
}
}
}
if (best != kNone) {
target[v] = best;
++n;
continue;
}
const uint64_t k = key(cx, cy, cz);
const size_t i = slot(k);
keys[i] = k;
next[v] = head[i];
head[i] = v;
}
}
if (merged) *merged = n;
return target;
}
Mesh weldByDistance(const Mesh& mesh, float distance, size_t* merged) {
size_t n = 0;
const std::vector<uint32_t> target = weldTargets(mesh, distance, &n);
if (merged) *merged = n;
return n ? remapped(mesh, target) : mesh;
}
const char* meshIssueName(MeshIssue issue) {
switch (issue) {
case MeshIssue::NonManifold: return "non_manifold";
case MeshIssue::Holes: return "holes";
case MeshIssue::Duplicate: return "duplicate";
case MeshIssue::Degenerate: return "degenerate";
case MeshIssue::ZeroArea: return "zero_area";
case MeshIssue::Flipped: return "flipped";
case MeshIssue::Isolated: return "isolated";
default: return "";
}
}
bool parseMeshIssue(const std::string& name, MeshIssue& out) {
for (int i = 0; i < kMeshIssueCount; ++i)
if (name == meshIssueName(MeshIssue(i))) {
out = MeshIssue(i);
return true;
}
return false;
}
size_t MeshReport::total() const {
size_t n = 0;
for (size_t c : count) n += c;
return n;
}
std::string MeshReport::summary() const {
static const char* const what[kMeshIssueCount][2] = {
{"non-manifold edge", "non-manifold edges"}, {"hole", "holes"},
{"duplicate triangle", "duplicate triangles"}, {"degenerate triangle", "degenerate triangles"},
{"zero-area triangle", "zero-area triangles"}, {"flipped triangle", "flipped triangles"},
{"isolated point", "isolated points"}};
std::string s;
for (int i = 0; i < kMeshIssueCount; ++i) {
if (!count[i]) continue;
if (!s.empty()) s += ", ";
s += std::to_string(count[i]) + " " + what[i][count[i] == 1 ? 0 : 1];
}
return s.empty() ? "No problems found" : s;
}
MeshReport checkMesh(const Mesh& mesh) {
MeshReport r;
auto& c = r.count;
const size_t nv = mesh.vertexCount(), nt = mesh.triangleCount();
// The per-triangle and per-point counts in parallel chunks, each with its own tally.
std::mutex lock;
parallelFor(nt, [&](size_t begin, size_t end) {
size_t degen = 0, dup = 0, zero = 0;
for (size_t t = begin; t < end; ++t) {
const glm::uvec3 tri = mesh.triangles[t];
if (degenerate(tri)) ++degen;
else if (duplicateOfEarlier(mesh, uint32_t(t))) ++dup;
else if (zeroArea(mesh, tri)) ++zero;
}
const std::lock_guard<std::mutex> hold(lock);
c[int(MeshIssue::Degenerate)] += degen;
c[int(MeshIssue::Duplicate)] += dup;
c[int(MeshIssue::ZeroArea)] += zero;
});
// Edges: non-manifold ones counted, open ones (one triangle) gathered to count the loops they form.
std::vector<std::pair<uint32_t, uint32_t>> open;
parallelFor(nv, [&](size_t begin, size_t end) {
size_t isolated = 0, nonManifold = 0;
std::vector<uint32_t> around;
std::vector<std::pair<uint32_t, uint32_t>> edges;
for (size_t a = begin; a < end; ++a) {
if (mesh.vertexTriangles(uint32_t(a)).size() == 0) {
++isolated;
continue;
}
for (uint32_t b : mesh.neighbors(uint32_t(a))) {
if (b <= a) continue;
edgeTriangles(mesh, uint32_t(a), b, around);
if (around.size() >= 3) ++nonManifold;
else if (around.size() == 1) edges.push_back({uint32_t(a), b});
}
}
const std::lock_guard<std::mutex> hold(lock);
c[int(MeshIssue::Isolated)] += isolated;
c[int(MeshIssue::NonManifold)] += nonManifold;
open.insert(open.end(), edges.begin(), edges.end());
});
// Holes: the connected sets of open edges (two loops touching at one point count as one).
if (!open.empty()) {
std::vector<uint32_t> points;
points.reserve(open.size() * 2);
for (const auto& [a, b] : open) points.insert(points.end(), {a, b});
std::sort(points.begin(), points.end());
points.erase(std::unique(points.begin(), points.end()), points.end());
auto index = [&](uint32_t v) { return uint32_t(std::lower_bound(points.begin(), points.end(), v) - points.begin()); };
UnionFind loops(points.size());
for (const auto& [a, b] : open) loops.unite(index(a), index(b));
size_t n = 0;
for (uint32_t i = 0; i < points.size(); ++i) n += loops.find(i) == i;
c[int(MeshIssue::Holes)] = n;
}
flipsNeeded(mesh, c[int(MeshIssue::Flipped)]);
return r;
}
bool fixMesh(const Mesh& mesh, MeshIssue issue, Mesh& out, size_t& fixed) {
const size_t nv = mesh.vertexCount(), nt = mesh.triangleCount();
fixed = 0;
switch (issue) {
case MeshIssue::Degenerate:
case MeshIssue::Duplicate: {
std::vector<uint8_t> drop(nt, 0);
for (uint32_t t = 0; t < nt; ++t) {
const bool d = degenerate(mesh.triangles[t]);
drop[t] = issue == MeshIssue::Degenerate ? d : !d && duplicateOfEarlier(mesh, t);
fixed += drop[t];
}
if (!fixed) return false;
out = withoutTriangles(mesh, drop);
return true;
}
case MeshIssue::ZeroArea: {
UnionFind points(nv);
for (uint32_t t = 0; t < nt; ++t) {
const glm::uvec3 tri = mesh.triangles[t];
if (degenerate(tri) || duplicateOfEarlier(mesh, t) || !zeroArea(mesh, tri)) continue;
int shortest = 0;
float best = INFINITY;
for (int k = 0; k < 3; ++k) {
const glm::vec3 e = mesh.positions[tri[(k + 1) % 3]] - mesh.positions[tri[k]];
if (glm::dot(e, e) < best) best = glm::dot(e, e), shortest = k;
}
points.unite(tri[shortest], tri[(shortest + 1) % 3]);
++fixed;
}
if (!fixed) return false;
std::vector<uint32_t> target(nv);
for (uint32_t v = 0; v < nv; ++v) target[v] = points.find(v);
out = remapped(mesh, target);
return true;
}
case MeshIssue::NonManifold: {
// Around each point of a non-manifold edge, its triangles fall into fans joined across ordinary edges (and
// across each non-manifold edge only by its kept pair); every fan past the first gets a copy of the point.
std::vector<uint8_t> onEdge(nv, 0);
std::vector<uint32_t> around;
for (uint32_t a = 0; a < nv; ++a)
for (uint32_t b : mesh.neighbors(a)) {
if (b <= a) continue;
edgeTriangles(mesh, a, b, around);
if (around.size() >= 3) {
onEdge[a] = onEdge[b] = 1;
++fixed;
}
}
if (!fixed) return false;
std::vector<glm::uvec3> corners(mesh.triangles);
std::vector<uint32_t> source(nv);
std::iota(source.begin(), source.end(), 0u);
std::vector<uint32_t> ring, fanOf;
for (uint32_t v = 0; v < nv; ++v) {
if (!onEdge[v]) continue;
ring.clear();
for (uint32_t t : mesh.vertexTriangles(v))
if (!degenerate(mesh.triangles[t])) ring.push_back(t);
std::sort(ring.begin(), ring.end());
UnionFind fans(ring.size());
auto at = [&](uint32_t t) { return uint32_t(std::lower_bound(ring.begin(), ring.end(), t) - ring.begin()); };
for (uint32_t w : mesh.neighbors(v)) {
edgeTriangles(mesh, v, w, around);
if (around.size() == 2) fans.unite(at(around[0]), at(around[1]));
else if (around.size() >= 3) {
const auto [p, q] = keptPair(mesh, std::min(v, w), std::max(v, w), around);
fans.unite(at(p), at(q));
}
}
fanOf.assign(ring.size(), kNone); // fan root -> the id its triangles use for v
for (size_t i = 0; i < ring.size(); ++i) {
const uint32_t root = fans.find(uint32_t(i));
if (root == 0) continue; // the first fan keeps the point
if (fanOf[root] == kNone) {
fanOf[root] = uint32_t(source.size());
source.push_back(v);
}
glm::uvec3& c = corners[ring[i]];
for (int k = 0; k < 3; ++k)
if (mesh.triangles[ring[i]][k] == v) c[k] = fanOf[root];
}
}
TriangleRebuild how;
how.corners = &corners;
how.source = &source;
out = rebuildTriangles(mesh, std::vector<uint8_t>(nt, 1), how);
return true;
}
case MeshIssue::Flipped: {
const std::vector<uint8_t> flip = flipsNeeded(mesh, fixed);
if (!fixed) return false;
TriangleRebuild how;
how.flip = &flip;
out = rebuildTriangles(mesh, std::vector<uint8_t>(nt, 1), how);
return true;
}
case MeshIssue::Isolated: {
for (uint32_t v = 0; v < nv; ++v) fixed += mesh.vertexTriangles(v).size() == 0;
if (!fixed) return false;
out = extractTriangles(mesh, std::vector<uint8_t>(nt, 1));
return true;
}
case MeshIssue::Holes: {
Mesh m = mesh;
CloseHolesStats stats;
std::string error;
if (!closeHoles(m, CloseHolesOptions{}, stats, error) || stats.filled == 0) return false;
fixed = stats.filled;
out = std::move(m);
return true;
}
default: return false;
}
}
void registerMeshCheckCommands(CommandRegistry& reg) {
using T = ParamSpec::Type;
reg.add({"weld_points",
"Merge by distance: merge the points of the active Part closer than a distance (one undo step). "
"Triangles that collapse are removed; each merged point takes the kept one's position and attributes.",
{{"distance", T::Number, "Largest distance between points that merge, in scene units (0 = only "
"points exactly on top of each other).", true},
{"preview", T::Bool, "Only count the points that would merge; change nothing.", false}},
[](Document& doc, const Args& a) -> CommandResult {
const double d = argNumber(a, "distance", 0.0);
if (!(d >= 0.0) || !std::isfinite(d)) return {false, "distance must be 0 or more"};
if (doc.mesh.vertexCount() == 0) return {false, "The mesh is empty"};
size_t n = 0;
if (argBool(a, "preview", false)) {
weldTargets(doc.mesh, float(d), &n);
return {true, std::to_string(n) + " points would merge"};
}
Mesh m = weldByDistance(doc.mesh, float(d), &n);
if (n == 0) return {false, "No points are that close"};
doc.replaceMeshUndoable(std::move(m), "Merge by Distance");
return {true, "Merged " + std::to_string(n) + " points, " + std::to_string(doc.mesh.vertexCount()) + " left"};
}});
reg.add({"mesh_check",
"Check the active Part for non-manifold edges, holes, duplicate, degenerate, zero-area and flipped "
"triangles and isolated points. Changes nothing (mesh_fix repairs).",
{},
[](Document& doc, const Args&) -> CommandResult {
const MeshReport r = checkMesh(doc.mesh);
std::string s = r.summary() + " (";
for (int i = 0; i < kMeshIssueCount; ++i)
s += std::string(i ? " " : "") + meshIssueName(MeshIssue(i)) + "=" + std::to_string(r.count[i]);
return {true, s + ")"};
}});
reg.add({"mesh_fix",
"Fix one kind of problem mesh_check finds, as one undo step: non_manifold (loosen the extra triangles), "
"holes (cap them), duplicate / degenerate (delete), zero_area (collapse), flipped (rewind), isolated "
"(remove). all fixes everything except holes (an open mesh may be open on purpose).",
{{"issue", T::String, "non_manifold, holes, duplicate, degenerate, zero_area, flipped, isolated or all.", true}},
[](Document& doc, const Args& a) -> CommandResult {
const std::string name = argString(a, "issue");
std::vector<MeshIssue> issues;
if (name == "all")
issues = {MeshIssue::Degenerate, MeshIssue::Duplicate, MeshIssue::ZeroArea, MeshIssue::NonManifold,
MeshIssue::Flipped, MeshIssue::Isolated};
else if (MeshIssue one; parseMeshIssue(name, one)) issues = {one};
else return {false, "Unknown issue '" + name + "'"};
Mesh current;
const Mesh* m = &doc.mesh;
std::string done;
for (MeshIssue issue : issues) {
Mesh next;
size_t fixed = 0;
if (!fixMesh(*m, issue, next, fixed)) continue;
current = std::move(next);
m = ¤t;
MeshReport one;
one.count[int(issue)] = fixed;
done += (done.empty() ? "" : ", ") + one.summary();
}
if (done.empty()) return {false, "Nothing to fix"};
doc.replaceMeshUndoable(std::move(current), "Fix Mesh");
return {true, "Fixed " + done};
}});
}
} // namespace sf