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/Dyntopo.h"
#include <algorithm>
#include <chrono>
#include <cmath>
#include <limits>
namespace sf {
namespace {
constexpr uint32_t kNone = ~0u;
// Calls f(meshArray, storedArray) for every per-vertex array of `m` an undo keeps (normals are recomputed).
template <class F>
void zipVertexArrays(Mesh& m, TopologyVertexValues& v, F&& f) {
f(m.positions, v.positions);
f(m.mask, v.mask);
f(m.colors, v.colors);
f(m.base, v.base);
f(m.paintBase, v.paintBase);
v.deltas.resize(m.layers.size());
for (size_t i = 0; i < m.layers.size(); ++i) f(m.layers[i].delta, v.deltas[i]);
v.paintColors.resize(m.paintLayers.size());
v.paintAlphas.resize(m.paintLayers.size());
for (size_t i = 0; i < m.paintLayers.size(); ++i) {
f(m.paintLayers[i].color, v.paintColors[i]);
f(m.paintLayers[i].alpha, v.paintAlphas[i]);
}
}
template <class F>
void zipTriangleArrays(Mesh& m, TopologyTriangleValues& t, F&& f) {
f(m.triangles, t.triangles);
f(m.facegroups, t.facegroups);
f(m.quadPartners, t.quadPartners);
f(m.hidden, t.hidden);
}
// Calls f(array) for every per-vertex array of `m` (normals included).
template <class F>
void forVertexArrays(Mesh& m, F&& f) {
f(m.positions);
f(m.normals);
f(m.mask);
f(m.colors);
f(m.base);
f(m.paintBase);
for (auto& l : m.layers) f(l.delta);
for (auto& l : m.paintLayers) {
f(l.color);
f(l.alpha);
}
}
template <class F>
void forTriangleArrays(Mesh& m, F&& f) {
f(m.triangles);
f(m.facegroups);
f(m.quadPartners);
f(m.hidden);
}
// Exchanges the values of `a` at `slots` with `stored` (the values of another state at the slots below
// `count`, in slot order) and resizes `a` to `count`. Absent arrays stay absent.
template <class T>
void swapSlots(std::vector<T>& a, const std::vector<uint32_t>& slots, std::vector<T>& stored, size_t count) {
if (a.empty()) return;
std::vector<T> current;
current.reserve(slots.size());
for (uint32_t s : slots)
if (s < a.size()) current.push_back(a[s]);
a.resize(count);
size_t k = 0;
for (uint32_t s : slots)
if (s < count && k < stored.size()) a[s] = stored[k++];
stored.swap(current);
}
template <class T>
size_t bytesOf(const std::vector<T>& v) {
return v.size() * sizeof(T);
}
bool setBit(std::vector<uint64_t>& bits, uint32_t i) {
if (size_t(i >> 6) >= bits.size()) bits.resize(size_t(i >> 6) + 1 + bits.size() / 4, 0);
const uint64_t b = uint64_t(1) << (i & 63);
if (bits[i >> 6] & b) return false;
bits[i >> 6] |= b;
return true;
}
float quality(const glm::vec3& a, const glm::vec3& b, const glm::vec3& c) {
// 1 for an equilateral triangle, 0 for a degenerate one.
const float area2 = glm::length(glm::cross(b - a, c - a));
const float sum = glm::dot(b - a, b - a) + glm::dot(c - b, c - b) + glm::dot(a - c, a - c);
return sum > 0.0f ? 3.4641016f * area2 / sum : 0.0f; // 4 sqrt(3) * area / sum, area = area2 / 2
}
} // namespace
float dyntopoEdgeLength(const DyntopoSettings& s, float radius, float diagonal) {
const float d = std::clamp(s.detail, 0.0f, 1.0f);
if (s.constantDetail) return std::max(diagonal, 1e-6f) * 0.05f * std::pow(0.04f, d); // diag/20 .. diag/500
return std::max(radius, 1e-7f) * 0.4f * std::pow(0.1f, d); // 0.4 .. 0.04 x the radius
}
std::string dyntopoBlocker(const Mesh& mesh) {
if (mesh.multires)
return "Dynamic topology needs a mesh without subdivision levels: Freeze Levels keeps the level shown and removes the others";
if (mesh.triangleCount() == 0) return "The mesh has no triangles";
if (!mesh.tube.empty()) return "This is a Tube Part: Bake it first (Tool > Tube > Bake)";
return {};
}
size_t TopologyVertexValues::bytes() const {
size_t n = bytesOf(positions) + bytesOf(colors) + bytesOf(base) + bytesOf(paintBase) + bytesOf(mask);
for (const auto& d : deltas) n += bytesOf(d);
for (const auto& d : paintColors) n += bytesOf(d);
for (const auto& d : paintAlphas) n += bytesOf(d);
return n;
}
size_t TopologyTriangleValues::bytes() const {
return bytesOf(triangles) + bytesOf(facegroups) + bytesOf(quadPartners) + bytesOf(hidden);
}
size_t TopologyUndo::bytes() const {
return vertices.bytes() + triangles.bytes() + bytesOf(vertexSlots) + bytesOf(triangleSlots) + bytesOf(uvs);
}
void TopologyUndo::swapWith(Mesh& mesh) {
const uint32_t nv = uint32_t(mesh.vertexCount()), nt = uint32_t(mesh.triangleCount());
zipVertexArrays(mesh, vertices, [&](auto& a, auto& stored) { swapSlots(a, vertexSlots, stored, vertexCount); });
zipTriangleArrays(mesh, triangles, [&](auto& a, auto& stored) { swapSlots(a, triangleSlots, stored, triangleCount); });
mesh.normals.resize(vertexCount, glm::vec3(0.0f, 1.0f, 0.0f));
std::swap(uvs, mesh.uvs);
vertexCount = nv;
triangleCount = nt;
}
// ---------------------------------------------------------------------------
// Recording and elements
// ---------------------------------------------------------------------------
void DynamicTopology::recordVertex(uint32_t v) {
if (!setBit(vertRec_, v)) return;
undo_->vertexSlots.push_back(v);
recordedNow_.push_back(v);
if (v < startVertices_)
zipVertexArrays(*mesh_, undo_->vertices, [&](auto& a, auto& stored) {
if (!a.empty()) stored.push_back(a[v]);
});
}
void DynamicTopology::recordTriangle(uint32_t t) {
if (!setBit(triRec_, t)) return;
undo_->triangleSlots.push_back(t);
if (t < startTriangles_)
zipTriangleArrays(*mesh_, undo_->triangles, [&](auto& a, auto& stored) {
if (!a.empty()) stored.push_back(a[t]);
});
}
void DynamicTopology::markVertex(uint32_t v) {
if (v >= changedVFlag_.size()) changedVFlag_.resize(size_t(v) + 1, 0);
if (changedVFlag_[v]) return;
changedVFlag_[v] = 1;
changedV_.push_back(v);
}
void DynamicTopology::markTriangle(uint32_t t) { changedT_.push_back(t); }
uint32_t DynamicTopology::newVertex() {
Mesh& m = *mesh_;
if (!freeV_.empty()) {
const uint32_t v = freeV_.back();
freeV_.pop_back();
deadV_[v] = 0;
return v; // (recorded when it died)
}
const uint32_t v = uint32_t(m.vertexCount());
recordVertex(v);
forVertexArrays(m, [&](auto& a) {
if (!a.empty()) a.emplace_back();
});
m.normals.resize(m.positions.size(), glm::vec3(0.0f, 1.0f, 0.0f)); // (a mesh without normals gets them)
m.addVertexSlot();
deadV_.push_back(0);
return v;
}
void DynamicTopology::interpolateVertex(uint32_t v, uint32_t a, uint32_t b, float t, const glm::vec3& position) {
Mesh& m = *mesh_;
recordVertex(v);
forVertexArrays(m, [&](auto& arr) {
if (!arr.empty()) arr[v] = arr[a] + (arr[b] - arr[a]) * t;
});
m.positions[v] = position;
const glm::vec3 n = m.normals[v];
const float len = glm::length(n);
m.normals[v] = len > 1e-20f ? n / len : glm::vec3(0.0f, 1.0f, 0.0f);
markVertex(v);
}
void DynamicTopology::killVertex(uint32_t v) {
recordVertex(v);
deadV_[v] = 1;
freeV_.push_back(v);
mesh_->setVertexTriangles(v, {});
mesh_->setNeighbors(v, {});
for (size_t k = 0; k < mirrorMaps_.size(); ++k) {
const uint32_t w = mirrorOf(k, v);
if (w == kNone) continue;
const size_t back = k < mirrorInverse_.size() ? mirrorInverse_[k] : k;
if (mirrorOf(back, w) == v) mirrorMaps_[back].stamp[w] = 0;
mirrorMaps_[k].stamp[v] = 0;
}
}
void DynamicTopology::vtInsert(uint32_t v, uint32_t t) {
const IndexRing r = mesh_->vertexTriangles(v);
scratch_.assign(r.begin(), r.end());
scratch_.insert(std::upper_bound(scratch_.begin(), scratch_.end(), t), t);
mesh_->setVertexTriangles(v, scratch_);
}
void DynamicTopology::vtErase(uint32_t v, uint32_t t) {
const IndexRing r = mesh_->vertexTriangles(v);
scratch_.assign(r.begin(), r.end());
auto it = std::lower_bound(scratch_.begin(), scratch_.end(), t);
if (it == scratch_.end() || *it != t) return;
scratch_.erase(it);
mesh_->setVertexTriangles(v, scratch_);
}
void DynamicTopology::vtReplace(uint32_t v, uint32_t from, uint32_t to) {
const IndexRing r = mesh_->vertexTriangles(v);
scratch_.assign(r.begin(), r.end());
auto it = std::lower_bound(scratch_.begin(), scratch_.end(), from);
if (it != scratch_.end() && *it == from) scratch_.erase(it);
scratch_.insert(std::upper_bound(scratch_.begin(), scratch_.end(), to), to);
mesh_->setVertexTriangles(v, scratch_);
}
void DynamicTopology::unpairQuad(uint32_t t) {
Mesh& m = *mesh_;
if (m.quadPartners.empty() || t >= m.quadPartners.size()) return;
const uint32_t p = m.quadPartners[t];
if (p == Mesh::kNoQuad) return;
recordTriangle(t);
m.quadPartners[t] = Mesh::kNoQuad;
if (p < m.quadPartners.size() && m.quadPartners[p] == t) {
recordTriangle(p);
m.quadPartners[p] = Mesh::kNoQuad;
markTriangle(p); // its wireframe now shows the old diagonal
}
}
uint32_t DynamicTopology::newTriangle(const glm::uvec3& tri, uint32_t like) {
Mesh& m = *mesh_;
uint32_t t;
if (!freeT_.empty()) {
t = freeT_.back();
freeT_.pop_back();
deadT_[t] = 0;
} else {
t = uint32_t(m.triangleCount());
recordTriangle(t);
forTriangleArrays(m, [&](auto& a) {
if (!a.empty()) a.emplace_back();
});
deadT_.push_back(0);
}
recordTriangle(t);
m.triangles[t] = tri;
if (!m.facegroups.empty()) m.facegroups[t] = m.facegroups[like];
if (!m.hidden.empty()) m.hidden[t] = m.hidden[like];
if (!m.quadPartners.empty()) m.quadPartners[t] = Mesh::kNoQuad;
for (int c = 0; c < 3; ++c) {
vtInsert(tri[c], t);
markVertex(tri[c]);
}
bvh_->insertTriangle(m, t, like);
markTriangle(t);
return t;
}
void DynamicTopology::setTriangle(uint32_t t, const glm::uvec3& tri) {
Mesh& m = *mesh_;
recordTriangle(t);
unpairQuad(t);
const glm::uvec3 old = m.triangles[t];
auto has = [](const glm::uvec3& x, uint32_t v) { return x.x == v || x.y == v || x.z == v; };
for (int c = 0; c < 3; ++c) {
if (!has(tri, old[c])) vtErase(old[c], t);
markVertex(old[c]);
}
for (int c = 0; c < 3; ++c) {
if (!has(old, tri[c])) vtInsert(tri[c], t);
markVertex(tri[c]);
}
m.triangles[t] = tri;
bvh_->touchTriangle(t);
markTriangle(t);
}
void DynamicTopology::killTriangle(uint32_t t) {
Mesh& m = *mesh_;
recordTriangle(t);
unpairQuad(t);
const glm::uvec3 tri = m.triangles[t];
for (int c = 0; c < 3; ++c) {
vtErase(tri[c], t);
markVertex(tri[c]);
}
bvh_->removeTriangle(t);
deadT_[t] = 1;
freeT_.push_back(t);
markTriangle(t);
}
void DynamicTopology::moveTriangle(uint32_t from, uint32_t to) {
Mesh& m = *mesh_;
recordTriangle(to);
recordTriangle(from);
forTriangleArrays(m, [&](auto& a) {
if (!a.empty()) a[to] = a[from];
});
if (!m.quadPartners.empty()) {
const uint32_t p = m.quadPartners[to];
if (p != Mesh::kNoQuad && p < m.quadPartners.size() && m.quadPartners[p] == from) {
recordTriangle(p);
m.quadPartners[p] = to;
}
}
const glm::uvec3 tri = m.triangles[to];
for (int c = 0; c < 3; ++c) vtReplace(tri[c], from, to);
bvh_->renumberTriangle(from, to);
markTriangle(to);
markTriangle(from);
}
void DynamicTopology::moveVertex(uint32_t from, uint32_t to) {
Mesh& m = *mesh_;
recordVertex(to);
recordVertex(from);
forVertexArrays(m, [&](auto& a) {
if (!a.empty()) a[to] = a[from];
});
const IndexRing tr = m.vertexTriangles(from);
scratch2_.assign(tr.begin(), tr.end());
m.setVertexTriangles(to, scratch2_);
for (uint32_t t : scratch2_) {
recordTriangle(t);
glm::uvec3& tri = m.triangles[t];
for (int c = 0; c < 3; ++c) {
if (tri[c] == from) tri[c] = to;
else markVertex(tri[c]); // its ring names `from`
}
markTriangle(t);
}
m.setVertexTriangles(from, {});
markVertex(to);
moved_.emplace_back(from, to);
}
// Fills the slots this remesh freed with the elements at the end of the arrays, so the mesh has no dead
// entries; then drops the end.
void DynamicTopology::compact() {
Mesh& m = *mesh_;
std::sort(freeT_.begin(), freeT_.end());
size_t nt = m.triangleCount();
for (uint32_t t : freeT_) {
while (nt > 0 && deadT_[nt - 1]) --nt;
if (t >= nt) break;
moveTriangle(uint32_t(nt - 1), t);
deadT_[t] = 0;
--nt;
}
forTriangleArrays(m, [&](auto& a) {
if (!a.empty()) a.resize(nt);
});
bvh_->resizeTriangles(nt);
deadT_.resize(nt); // (every slot below nt is live again)
freeT_.clear();
std::sort(freeV_.begin(), freeV_.end());
const size_t before = m.vertexCount();
size_t nv = before;
for (uint32_t v : freeV_) {
while (nv > 0 && deadV_[nv - 1]) --nv;
if (v >= nv) break;
moveVertex(uint32_t(nv - 1), v);
deadV_[v] = 0;
--nv;
}
forVertexArrays(m, [&](auto& a) {
if (!a.empty()) a.resize(nv);
});
for (size_t i = nv; i < before; ++i) m.removeLastVertexSlot();
deadV_.resize(nv);
freeV_.clear();
}
// ---------------------------------------------------------------------------
// Queries
// ---------------------------------------------------------------------------
int DynamicTopology::edgeTriangles(uint32_t a, uint32_t b, uint32_t* out) const {
int n = 0;
for (uint32_t t : mesh_->vertexTriangles(a)) {
const glm::uvec3& tri = mesh_->triangles[t];
if (tri.x == b || tri.y == b || tri.z == b) {
if (n < 4) out[n] = t;
++n;
}
}
return n;
}
void DynamicTopology::ring(uint32_t v, std::vector<uint32_t>& out) const {
out.clear();
for (uint32_t t : mesh_->vertexTriangles(v)) {
const glm::uvec3& tri = mesh_->triangles[t];
for (int c = 0; c < 3; ++c)
if (tri[c] != v) out.push_back(tri[c]);
}
std::sort(out.begin(), out.end());
out.erase(std::unique(out.begin(), out.end()), out.end());
}
float DynamicTopology::len2(uint32_t a, uint32_t b) const {
const glm::vec3 d = mesh_->positions[a] - mesh_->positions[b];
return glm::dot(d, d);
}
// The edge passes within the brush radius of the dab's centre (with `mirrored`, or of one of its mirror images).
bool DynamicTopology::inside(uint32_t a, uint32_t b, bool mirrored) const {
const glm::vec3 p = mesh_->positions[a], d = mesh_->positions[b] - p;
const float dd = glm::dot(d, d);
auto within = [&](const glm::vec3& c) {
const float t = dd > 0.0f ? std::clamp(glm::dot(c - p, d) / dd, 0.0f, 1.0f) : 0.0f;
const glm::vec3 q = p + d * t - c;
return glm::dot(q, q) <= radius_ * radius_;
};
if (within(center_)) return true;
if (!mirrored) return false;
for (const SymCopy& s : mirrorSigns_)
if (within(s.point(center_))) return true;
return false;
}
// Operations are found on the brush's side and done on every side at once (orbit), which needs each edge's
// mirror images. A mesh whose sides aren't mirrored (QRemesh's quads, a model edited without symmetry) has none
// to find, and its other sides were left coarse while the brush moved them too (#23): an edge under a mirror
// image of the brush whose own images are missing is remeshed where it is, as the brush's side is.
bool DynamicTopology::candidate(uint32_t a, uint32_t b) const {
if (inside(a, b)) return true;
if (mirrorSigns_.empty() || !inside(a, b, true)) return false;
orbit(a, b, orbitScratch_);
return orbitIncomplete_;
}
// The triangles under the brush and under its mirror images (for the edges candidate() takes there), and the
// slivers under all of them: a brush can squash a triangle on one side only (overlapping mirrored dabs), and
// they must be repaired where they are.
void DynamicTopology::queryRegion() {
bvh_->queryTriangles(*mesh_, center_, radius_, regionTris_);
mirrorTris_.clear();
slivers_.clear();
const auto& p = mesh_->positions;
auto addSlivers = [&](const std::vector<uint32_t>& tris) {
for (uint32_t t : tris) {
const glm::uvec3& tri = mesh_->triangles[t];
if (quality(p[tri.x], p[tri.y], p[tri.z]) < 0.05f) slivers_.push_back(t);
}
};
addSlivers(regionTris_);
std::vector<uint32_t> more;
for (const SymCopy& s : mirrorSigns_) {
bvh_->queryTriangles(*mesh_, s.point(center_), radius_, more);
addSlivers(more);
mirrorTris_.insert(mirrorTris_.end(), more.begin(), more.end());
}
std::sort(mirrorTris_.begin(), mirrorTris_.end());
mirrorTris_.erase(std::unique(mirrorTris_.begin(), mirrorTris_.end()), mirrorTris_.end());
std::sort(slivers_.begin(), slivers_.end());
slivers_.erase(std::unique(slivers_.begin(), slivers_.end()), slivers_.end());
}
// Left alone: fully masked, next to a hidden triangle, on a non-manifold edge, or without triangles.
bool DynamicTopology::locked(uint32_t v) const {
const Mesh& m = *mesh_;
if (deadV_[v]) return true;
if (m.maskAt(v) >= 1.0f - 1e-4f) return true;
const IndexRing tris = m.vertexTriangles(v);
if (tris.empty()) return true;
if (m.hasHidden())
for (uint32_t t : tris)
if (m.hidden[t]) return true;
// Each neighbour shares one (boundary) or two triangles with v; more is non-manifold. (A small table for the
// usual valences; sorting for the rare fan with more neighbours.)
if (tris.size() <= 32) {
uint32_t other[96], count[96];
int n = 0;
for (uint32_t t : tris) {
const glm::uvec3& tri = m.triangles[t];
for (int c = 0; c < 3; ++c) {
if (tri[c] == v) continue;
int i = 0;
while (i < n && other[i] != tri[c]) ++i;
if (i == n) {
other[n] = tri[c];
count[n++] = 0;
}
if (++count[i] > 2) return true;
}
}
return false;
}
std::vector<uint32_t>& others = lockScratch_;
others.clear();
for (uint32_t t : tris) {
const glm::uvec3& tri = m.triangles[t];
for (int c = 0; c < 3; ++c)
if (tri[c] != v) others.push_back(tri[c]);
}
std::sort(others.begin(), others.end());
for (size_t i = 0; i + 2 < others.size(); ++i)
if (others[i] == others[i + 2]) return true;
return false;
}
bool DynamicTopology::planeVertex(uint32_t v) const {
for (size_t k = 0; k < mirrorMaps_.size(); ++k)
if (mirrorOf(k, v) == v) return true;
return false;
}
// Boundary, face group border, non-manifold, or lying in a symmetry plane.
bool DynamicTopology::featureEdge(uint32_t a, uint32_t b) const {
uint32_t tris[4];
const int n = edgeTriangles(a, b, tris);
if (n != 2) return true;
if (mesh_->facegroupAt(tris[0]) != mesh_->facegroupAt(tris[1])) return true;
for (size_t k = 0; k < mirrorMaps_.size(); ++k)
if (mirrorOf(k, a) == a && mirrorOf(k, b) == b) return true;
return false;
}
// The number of feature edges at v (the other ends of the first two in `other`), or 3 for a corner: a vertex
// in a symmetry plane is a corner unless exactly two of its edges lie in that plane.
int DynamicTopology::featureEdges(uint32_t v, uint32_t* other) const {
ring(v, scratch_);
int n = 0;
for (uint32_t u : scratch_)
if (featureEdge(v, u)) {
if (n < 2) other[n] = u;
++n;
}
if (n == 0 && planeVertex(v)) return 3;
return std::min(n, 3);
}
bool DynamicTopology::boundaryVertex(uint32_t v) const {
ring(v, scratch2_);
uint32_t tris[4];
for (uint32_t u : scratch2_)
if (edgeTriangles(v, u, tris) == 1) return true;
return false;
}
glm::vec3 DynamicTopology::faceNormalAt(uint32_t v) const {
glm::vec3 n(0.0f);
const auto& p = mesh_->positions;
for (uint32_t t : mesh_->vertexTriangles(v)) {
const glm::uvec3& tri = mesh_->triangles[t];
n += glm::cross(p[tri.y] - p[tri.x], p[tri.z] - p[tri.x]);
}
const float len = glm::length(n);
return len > 1e-30f ? n / len : glm::vec3(0.0f);
}
// ---------------------------------------------------------------------------
// Symmetry
// ---------------------------------------------------------------------------
uint32_t DynamicTopology::mirrorOf(size_t k, uint32_t v) const {
const MirrorMap& map = mirrorMaps_[k];
return v < map.to.size() && map.stamp[v] == mirrorStamp_ ? map.to[v] : kNone;
}
void DynamicTopology::setMirror(size_t k, uint32_t v, uint32_t w) {
MirrorMap& map = mirrorMaps_[k];
const size_t need = size_t(std::max(v, w)) + 1;
if (map.to.size() < need) {
map.to.resize(need + need / 4, kNone);
map.stamp.resize(need + need / 4, 0);
}
map.to[v] = w;
map.stamp[v] = mirrorStamp_;
// The inverse copy maps w back to v (the same map for a mirror).
MirrorMap& back = mirrorMaps_[k < mirrorInverse_.size() ? mirrorInverse_[k] : k];
if (back.to.size() < need) {
back.to.resize(need + need / 4, kNone);
back.stamp.resize(need + need / 4, 0);
}
back.to[w] = v;
back.stamp[w] = mirrorStamp_;
}
// Pairs each vertex with the vertex at its mirror image (within eps_), for every mirror; only pairs that
// find each other both ways count. The match is loose because overlapping mirrored dabs near the plane don't
// move both sides exactly alike, but vertices are rarely closer than half an edge.
void DynamicTopology::matchMirrors(const std::vector<uint32_t>& verts) {
const Mesh& m = *mesh_;
// A grid of cells twice the tolerance (an open-addressing table of the occupied cells): a point's nearest
// vertex within the tolerance is in one of the 2 x 2 x 2 cells around it.
const float cell = std::max(eps_ * 2.0f, 1e-12f);
auto cellOf = [cell](const glm::vec3& p) { return glm::ivec3(glm::floor(p / cell)); };
auto keyOf = [](const glm::ivec3& q) {
return (uint64_t(uint32_t(q.x) & 0x1FFFFF) << 42) | (uint64_t(uint32_t(q.y) & 0x1FFFFF) << 21) | uint64_t(uint32_t(q.z) & 0x1FFFFF);
};
// Each occupied cell's first vertex in the table, the rest chained through gridNext_.
size_t slots = 16;
while (slots < verts.size() * 2) slots *= 2;
gridKeys_.assign(slots, ~uint64_t(0));
gridHead_.resize(slots);
gridNext_.resize(verts.size());
auto slotOf = [&](uint64_t key) {
size_t h = size_t((key * 0x9E3779B97F4A7C15ull) >> 20) & (slots - 1);
while (gridKeys_[h] != ~uint64_t(0) && gridKeys_[h] != key) h = (h + 1) & (slots - 1);
return h;
};
for (uint32_t i = 0; i < verts.size(); ++i) {
const uint64_t key = keyOf(cellOf(m.positions[verts[i]]));
const size_t h = slotOf(key);
gridNext_[i] = gridKeys_[h] == key ? gridHead_[h] : kNone;
gridKeys_[h] = key;
gridHead_[h] = i;
}
auto nearest = [&](const glm::vec3& p) {
uint32_t best = kNone;
float bestD = eps_ * eps_;
const glm::vec3 f = p / cell;
const glm::ivec3 q = glm::ivec3(glm::floor(f));
const glm::ivec3 step(f.x - float(q.x) < 0.5f ? -1 : 1, f.y - float(q.y) < 0.5f ? -1 : 1, f.z - float(q.z) < 0.5f ? -1 : 1);
for (int c = 0; c < 8; ++c) {
const glm::ivec3 at = q + glm::ivec3(c & 1 ? step.x : 0, c & 2 ? step.y : 0, c & 4 ? step.z : 0);
const uint64_t key = keyOf(at);
const size_t h = slotOf(key);
if (gridKeys_[h] != key) continue;
for (uint32_t i = gridHead_[h]; i != kNone; i = gridNext_[i]) {
const uint32_t w = verts[i];
const glm::vec3 d = m.positions[w] - p;
const float dd = glm::dot(d, d);
if (dd < bestD || (dd == bestD && best != kNone && w < best)) {
bestD = dd;
best = w;
}
}
}
return best;
};
for (size_t k = 0; k < mirrorSigns_.size(); ++k) {
const SymCopy& s = mirrorSigns_[k];
for (uint32_t v : verts) {
if (mirrorOf(k, v) != kNone) continue; // (its partner found it first)
const uint32_t w = nearest(s.point(m.positions[v]));
if (w == kNone || nearest(s.inversePoint(m.positions[w])) != v) continue;
setMirror(k, v, w);
}
}
}
// The edge a-b and its distinct mirror images (each once, either direction).
void DynamicTopology::orbit(uint32_t a, uint32_t b, std::vector<std::pair<uint32_t, uint32_t>>& out) const {
out.assign(1, {a, b});
orbitIncomplete_ = false;
uint32_t tris[4];
for (size_t k = 0; k < mirrorMaps_.size(); ++k) {
const uint32_t ma = mirrorOf(k, a), mb = mirrorOf(k, b);
if (ma == kNone || mb == kNone || ma == mb || edgeTriangles(ma, mb, tris) == 0) {
orbitIncomplete_ = true;
continue;
}
bool seen = false;
for (const auto& e : out) seen = seen || (e.first == ma && e.second == mb) || (e.first == mb && e.second == ma);
if (!seen && edgeTriangles(ma, mb, tris) > 0) out.emplace_back(ma, mb);
}
}
bool DynamicTopology::orbitSharesTriangle(const std::vector<std::pair<uint32_t, uint32_t>>& edges) const {
uint32_t ti[4], tj[4];
for (size_t i = 0; i < edges.size(); ++i) {
const int ni = std::min(4, edgeTriangles(edges[i].first, edges[i].second, ti));
for (size_t j = i + 1; j < edges.size(); ++j) {
const int nj = std::min(4, edgeTriangles(edges[j].first, edges[j].second, tj));
for (int x = 0; x < ni; ++x)
for (int y = 0; y < nj; ++y)
if (ti[x] == tj[y]) return true;
// Sharing a vertex is enough to make the order of the two operations matter.
const auto& e = edges[i];
const auto& f = edges[j];
if (e.first == f.first || e.first == f.second || e.second == f.first || e.second == f.second) return true;
}
}
return false;
}
// ---------------------------------------------------------------------------
// Operations
// ---------------------------------------------------------------------------
// Splits edge a-b at its midpoint: each triangle on it becomes two. Returns the new vertex (kNone if the
// edge isn't a manifold one).
uint32_t DynamicTopology::split(uint32_t a, uint32_t b) {
Mesh& m = *mesh_;
uint32_t tris[4];
const int n = edgeTriangles(a, b, tris);
if (n < 1 || n > 2) return kNone;
// On the curve the end normals describe (a PN-triangle edge's midpoint), not the chord: splitting a
// coarse curved surface then keeps it round instead of showing its old flat facets. Kept within a quarter
// of the edge, for creases.
const glm::vec3 pa = m.positions[a], pb = m.positions[b];
glm::vec3 bend(0.0f);
if (m.normals.size() == m.vertexCount()) {
const glm::vec3 na = m.normals[a], nb = m.normals[b], e = pb - pa;
bend = (na * glm::dot(e, na) - nb * glm::dot(e, nb)) * -0.125f;
const float len = glm::length(bend), limit = 0.25f * glm::length(e);
if (!std::isfinite(len)) bend = glm::vec3(0.0f);
else if (len > limit) bend *= limit / len;
}
const glm::vec3 mid = (pa + pb) * 0.5f + bend;
// Splitting a triangle squashed flat only makes more flat ones (collapses and flips repair those).
const float minArea = 1e-6f * target_ * target_;
for (int i = 0; i < n; ++i) {
const glm::uvec3& tri = m.triangles[tris[i]];
uint32_t c = tri.x;
for (int k = 0; k < 3; ++k)
if (tri[k] != a && tri[k] != b) c = tri[k];
const glm::vec3 pc = m.positions[c];
if (glm::length(glm::cross(mid - pa, pc - pa)) < minArea || glm::length(glm::cross(pb - mid, pc - mid)) < minArea) return kNone;
}
const uint32_t v = newVertex();
interpolateVertex(v, a, b, 0.5f, mid);
if (!m.base.empty()) m.base[v] += bend; // (sculpt layers: positions stay base + offsets)
for (int i = 0; i < n; ++i) {
const uint32_t t = tris[i];
glm::uvec3 tri = m.triangles[t];
int k = 0;
while (k < 3 && !((tri[k] == a && tri[(k + 1) % 3] == b) || (tri[k] == b && tri[(k + 1) % 3] == a))) ++k;
if (k == 3) continue;
const uint32_t x = tri[k], y = tri[(k + 1) % 3], c = tri[(k + 2) % 3];
glm::uvec3 first = tri;
first[(k + 1) % 3] = v; // (x, v, c) in t's own rotation
setTriangle(t, first);
newTriangle(glm::uvec3(v, y, c), t);
(void)x;
}
++stats.splits;
++ops_;
return v;
}
void DynamicTopology::pushEdgesAround(uint32_t v, bool longer) {
ring(v, scratch2_);
for (uint32_t u : scratch2_) {
if (deadV_[u] || !candidate(v, u)) continue;
const float l = len2(v, u);
if (longer ? l > splitLen2_ : l < collapseLen2_) {
heap_.push_back({longer ? l : -l, std::min(u, v), std::max(u, v)});
std::push_heap(heap_.begin(), heap_.end(), [](const Edge& x, const Edge& y) {
return x.len2 != y.len2 ? x.len2 < y.len2 : x.a != y.a ? x.a > y.a : x.b > y.b;
});
}
}
}
void DynamicTopology::splitOrbit(uint32_t a, uint32_t b, int depth) {
std::vector<std::pair<uint32_t, uint32_t>> edges;
orbit(a, b, edges);
// Two images of the edge on one triangle (a triangle across the symmetry plane): split its third edge,
// which crosses the plane, first, so the two images end up apart and the result stays mirrored.
if (edges.size() > 1 && depth < 3) {
uint32_t ti[4], tj[4];
bool again = false;
for (size_t i = 0; i < edges.size() && !again; ++i) {
const int ni = std::min(4, edgeTriangles(edges[i].first, edges[i].second, ti));
for (size_t j = i + 1; j < edges.size() && !again; ++j) {
const int nj = std::min(4, edgeTriangles(edges[j].first, edges[j].second, tj));
for (int x = 0; x < ni && !again; ++x)
for (int y = 0; y < nj && !again; ++y) {
if (ti[x] != tj[y]) continue;
const glm::uvec3 tri = mesh_->triangles[ti[x]];
// The corner on neither edge... the third edge joins the two corners other than the shared one.
uint32_t shared = kNone;
for (uint32_t c : {edges[i].first, edges[i].second})
if (c == edges[j].first || c == edges[j].second) shared = c;
if (shared == kNone) continue;
uint32_t p = kNone, q = kNone;
for (int c = 0; c < 3; ++c)
if (tri[c] != shared) (p == kNone ? p : q) = tri[c];
if (p != kNone && q != kNone && !locked(p) && !locked(q)) {
splitOrbit(p, q, depth + 1);
again = true;
}
}
}
}
if (again) orbit(a, b, edges);
}
if (orbitIncomplete_ && !mirrorMaps_.empty()) ++stats.unpaired;
std::vector<uint32_t> made(edges.size(), kNone);
uint32_t tris[4];
for (size_t i = 0; i < edges.size(); ++i) {
const auto [x, y] = edges[i];
const int n = edgeTriangles(x, y, tris);
if (n < 1 || n > 2 || locked(x) || locked(y)) continue;
made[i] = split(x, y);
}
// The new vertices are each other's mirror images as their edges were.
for (size_t k = 0; k < mirrorMaps_.size(); ++k)
for (size_t i = 0; i < edges.size(); ++i) {
if (made[i] == kNone) continue;
const uint32_t ma = mirrorOf(k, edges[i].first), mb = mirrorOf(k, edges[i].second);
for (size_t j = 0; j < edges.size(); ++j)
if (made[j] != kNone && ((edges[j].first == ma && edges[j].second == mb) ||
(edges[j].first == mb && edges[j].second == ma)))
setMirror(k, made[i], made[j]);
}
for (uint32_t v : made)
if (v != kNone) pushEdgesAround(v, true);
}
void DynamicTopology::splitPass() {
heap_.clear();
uint32_t tris[4];
for (uint32_t t : regionTris_) {
const glm::uvec3 tri = mesh_->triangles[t];
for (int c = 0; c < 3; ++c) {
const uint32_t a = tri[c], b = tri[(c + 1) % 3];
// Each edge once: from the triangle where it runs upwards (a boundary edge from its only one).
if (a > b && edgeTriangles(a, b, tris) != 1) continue;
const float l = len2(a, b);
if (l > splitLen2_ && inside(a, b)) heap_.push_back({l, std::min(a, b), std::max(a, b)});
}
}
// Under the mirror images: only edges whose image on the brush's side is missing (the others are split
// with it, by splitOrbit).
for (uint32_t t : mirrorTris_) {
const glm::uvec3 tri = mesh_->triangles[t];
for (int c = 0; c < 3; ++c) {
const uint32_t a = tri[c], b = tri[(c + 1) % 3];
if (a > b && edgeTriangles(a, b, tris) != 1) continue;
const float l = len2(a, b);
if (l > splitLen2_ && !inside(a, b) && candidate(a, b)) heap_.push_back({l, std::min(a, b), std::max(a, b)});
}
}
auto less = [](const Edge& x, const Edge& y) {
return x.len2 != y.len2 ? x.len2 < y.len2 : x.a != y.a ? x.a > y.a : x.b > y.b;
};
std::make_heap(heap_.begin(), heap_.end(), less);
while (!heap_.empty() && ops_ < maxOps_) {
std::pop_heap(heap_.begin(), heap_.end(), less);
const Edge e = heap_.back();
heap_.pop_back();
if (deadV_[e.a] || deadV_[e.b]) continue;
const int n = edgeTriangles(e.a, e.b, tris);
if (n < 1 || n > 2 || len2(e.a, e.b) <= splitLen2_) continue;
if (locked(e.a) || locked(e.b)) continue;
splitOrbit(e.a, e.b, 0);
}
}
// Which end of edge a-b goes and where the other one ends up: a free vertex (no feature edges) goes onto a
// feature vertex, or both meet at the midpoint; a vertex on a feature curve (two feature edges) only slides
// along it onto the next vertex of the curve; corners stay.
bool DynamicTopology::collapseTarget(uint32_t a, uint32_t b, uint32_t& keep, uint32_t& drop, glm::vec3& p) const {
uint32_t oa[2], ob[2];
const int fa = featureEdges(a, oa), fb = featureEdges(b, ob);
const auto& pos = mesh_->positions;
if (fa == 0 && fb == 0) {
keep = std::min(a, b);
drop = std::max(a, b);
p = (pos[a] + pos[b]) * 0.5f;
return true;
}
if (fa == 0) {
keep = b, drop = a, p = pos[b];
return true;
}
if (fb == 0) {
keep = a, drop = b, p = pos[a];
return true;
}
if (!featureEdge(a, b)) return false;
if (fa == 2 && (oa[0] == b || oa[1] == b)) {
keep = b, drop = a, p = pos[b];
return true;
}
if (fb == 2 && (ob[0] == a || ob[1] == a)) {
keep = a, drop = b, p = pos[a];
return true;
}
return false;
}
bool DynamicTopology::canCollapse(uint32_t keep, uint32_t drop, const glm::vec3& p) const {
const Mesh& m = *mesh_;
uint32_t tris[4];
const int n = edgeTriangles(keep, drop, tris);
if (n < 1 || n > 2) return false;
uint32_t opposite[2] = {kNone, kNone};
for (int i = 0; i < n; ++i) {
const glm::uvec3& tri = m.triangles[tris[i]];
for (int c = 0; c < 3; ++c)
if (tri[c] != keep && tri[c] != drop) opposite[i] = tri[c];
if (opposite[i] == kNone) return false;
}
if (n == 2 && opposite[0] == opposite[1]) return false;
std::vector<uint32_t>& rk = ringA_;
std::vector<uint32_t>& rd = ringB_;
ring(keep, rk);
ring(drop, rd);
// Link condition: the ends share exactly the neighbours across the edge's triangles (else the surface
// would pinch).
size_t common = 0;
for (uint32_t u : rk)
if (std::binary_search(rd.begin(), rd.end(), u)) {
if (u != opposite[0] && u != opposite[1]) return false;
++common;
}
if (common != size_t(n)) return false;
// Nobody left with fewer than three neighbours (no flat double triangles).
if (rk.size() + rd.size() - size_t(n) - 2 < 3) return false;
std::vector<uint32_t>& ro = ringC_;
for (int i = 0; i < n; ++i) {
ring(opposite[i], ro);
if (ro.size() <= 3) return false;
}
if (n == 1 && (rk.size() < 3 || rd.size() < 3)) return false;
// No long edge, no triangle turned over or made degenerate or much worse.
const auto& pos = m.positions;
// (Only what the collapse makes worse counts: merging two vertices at one point moves nothing.)
for (uint32_t end : {keep, drop})
for (uint32_t u : end == keep ? rk : rd)
if (u != keep && u != drop) {
const glm::vec3 d = pos[u] - p;
const float l = glm::dot(d, d);
if (l >= splitLen2_ && l > len2(u, end) * 1.0001f) return false;
}
const float minArea = 1e-4f * target_ * target_;
for (uint32_t v : {keep, drop})
for (uint32_t t : m.vertexTriangles(v)) {
if (t == tris[0] || (n == 2 && t == tris[1])) continue;
const glm::uvec3& tri = m.triangles[t];
glm::vec3 q[3], o[3];
for (int c = 0; c < 3; ++c) {
o[c] = pos[tri[c]];
q[c] = tri[c] == keep || tri[c] == drop ? p : o[c];
}
const glm::vec3 nOld = glm::cross(o[1] - o[0], o[2] - o[0]);
const glm::vec3 nNew = glm::cross(q[1] - q[0], q[2] - q[0]);
const float lNew = glm::length(nNew), lOld = glm::length(nOld);
if (lNew < minArea && lNew < lOld * 0.999f) return false;
// (A triangle already squashed flat has no direction to keep: it is being repaired, not turned over.)
if (lOld >= minArea && glm::dot(nOld, nNew) <= 0.3f * lOld * lNew) return false;
const float qNew = quality(q[0], q[1], q[2]);
if (qNew < 0.1f && qNew < quality(o[0], o[1], o[2])) return false;
}
return true;
}
void DynamicTopology::collapse(uint32_t keep, uint32_t drop, const glm::vec3& p) {
Mesh& m = *mesh_;
uint32_t tris[4];
const int n = edgeTriangles(keep, drop, tris);
for (int i = 0; i < n && i < 2; ++i) killTriangle(tris[i]);
const IndexRing around = m.vertexTriangles(drop);
std::vector<uint32_t>& list = ringA_;
list.assign(around.begin(), around.end());
for (uint32_t t : list) {
glm::uvec3 tri = m.triangles[t];
for (int c = 0; c < 3; ++c)
if (tri[c] == drop) tri[c] = keep;
setTriangle(t, tri);
}
const bool midpoint = p != m.positions[keep];
if (midpoint) interpolateVertex(keep, keep, drop, 0.5f, p);
markVertex(keep);
killVertex(drop);
++stats.collapses;
++ops_;
}
void DynamicTopology::collapsePass() {
heap_.clear();
uint32_t tris[4];
for (uint32_t t : regionTris_) {
if (t >= mesh_->triangleCount() || deadT_[t]) continue;
const glm::uvec3 tri = mesh_->triangles[t];
for (int c = 0; c < 3; ++c) {
const uint32_t a = tri[c], b = tri[(c + 1) % 3];
if (a > b && edgeTriangles(a, b, tris) != 1) continue;
const float l = len2(a, b);
if (l < collapseLen2_ && inside(a, b)) heap_.push_back({-l, std::min(a, b), std::max(a, b)});
}
}
for (uint32_t t : mirrorTris_) { // (as in splitPass)
if (t >= mesh_->triangleCount() || deadT_[t]) continue;
const glm::uvec3 tri = mesh_->triangles[t];
for (int c = 0; c < 3; ++c) {
const uint32_t a = tri[c], b = tri[(c + 1) % 3];
if (a > b && edgeTriangles(a, b, tris) != 1) continue;
const float l = len2(a, b);
if (l < collapseLen2_ && !inside(a, b) && candidate(a, b)) heap_.push_back({-l, std::min(a, b), std::max(a, b)});
}
}
for (uint32_t t : slivers_) {
if (t >= mesh_->triangleCount() || deadT_[t]) continue;
const glm::uvec3 tri = mesh_->triangles[t];
for (int c = 0; c < 3; ++c) {
const uint32_t a = tri[c], b = tri[(c + 1) % 3];
const float l = len2(a, b);
if (l < collapseLen2_ && inside(a, b, true)) heap_.push_back({-l, std::min(a, b), std::max(a, b)});
}
}
auto less = [](const Edge& x, const Edge& y) {
return x.len2 != y.len2 ? x.len2 < y.len2 : x.a != y.a ? x.a > y.a : x.b > y.b;
};
std::make_heap(heap_.begin(), heap_.end(), less);
std::vector<std::pair<uint32_t, uint32_t>> edges;
struct Plan {
uint32_t keep, drop;
glm::vec3 p;
};
std::vector<Plan> plans;
while (!heap_.empty() && ops_ < maxOps_) {
std::pop_heap(heap_.begin(), heap_.end(), less);
const Edge e = heap_.back();
heap_.pop_back();
if (deadV_[e.a] || deadV_[e.b]) continue;
const int n = edgeTriangles(e.a, e.b, tris);
if (n < 1 || n > 2 || len2(e.a, e.b) >= collapseLen2_) continue;
if (locked(e.a) || locked(e.b)) continue;
orbit(e.a, e.b, edges);
if (edges.size() > 1 && orbitSharesTriangle(edges)) continue; // at the symmetry plane: leave it
plans.clear();
bool ok = true;
for (const auto& [x, y] : edges) {
Plan pl;
if (locked(x) || locked(y) || !collapseTarget(x, y, pl.keep, pl.drop, pl.p) || !canCollapse(pl.keep, pl.drop, pl.p)) {
ok = false;
break;
}
plans.push_back(pl);
}
if (!ok) continue;
if (orbitIncomplete_ && !mirrorMaps_.empty()) ++stats.unpaired;
for (size_t i = 0; i < plans.size(); ++i) {
const Plan& pl = plans[i];
if (deadV_[pl.keep] || deadV_[pl.drop]) continue;
if (i > 0 && !canCollapse(pl.keep, pl.drop, pl.p)) continue; // (the first changed its surroundings)
collapse(pl.keep, pl.drop, pl.p);
pushEdgesAround(pl.keep, false);
}
}
}
// Flipping a-b (between triangles a,b,c and b,a,d) to c-d: worth it when it brings the four valences closer
// to 6 (4 on a boundary) without folding or flattening the surface.
bool DynamicTopology::flipGain(uint32_t a, uint32_t b, uint32_t& c, uint32_t& d) const {
const Mesh& m = *mesh_;
uint32_t tris[4];
if (edgeTriangles(a, b, tris) != 2 || featureEdge(a, b)) return false;
c = d = kNone;
for (int i = 0; i < 2; ++i) {
const glm::uvec3& tri = m.triangles[tris[i]];
int k = 0;
while (k < 3 && tri[k] != a) ++k;
if (k == 3) return false;
const uint32_t next = tri[(k + 1) % 3], third = tri[(k + 2) % 3];
if (next == b) c = third; // a -> b: the triangle a, b, c
else d = next; // b -> a: the triangle b, a, d
}
if (c == kNone || d == kNone || c == d) return false;
uint32_t tmp[4];
if (edgeTriangles(c, d, tmp) > 0) return false;
const auto& p = m.positions;
const glm::vec3 n1 = glm::cross(p[b] - p[a], p[c] - p[a]), n2 = glm::cross(p[a] - p[b], p[d] - p[b]);
const float l1 = glm::length(n1), l2 = glm::length(n2);
const glm::vec3 m1 = glm::cross(p[a] - p[c], p[d] - p[c]), m2 = glm::cross(p[b] - p[d], p[c] - p[d]);
const float k1 = glm::length(m1), k2 = glm::length(m2);
const float minArea = 1e-4f * target_ * target_;
if (k1 < minArea || k2 < minArea) return false;
const float qOld = std::min(quality(p[a], p[b], p[c]), quality(p[b], p[a], p[d]));
const float qNew = std::min(quality(p[c], p[a], p[d]), quality(p[d], p[b], p[c]));
const glm::vec3 nSum = n1 + n2;
if (glm::dot(m1, nSum) <= 0.0f || glm::dot(m2, nSum) <= 0.0f) return false;
// A sliver (a triangle squashed flat, its normal meaningless) is flipped whenever that makes both clearly
// better, whatever the valences: collapses can't always reach it, and splitting it only makes more.
if (qOld < 0.05f) {
ring(a, ringC_);
if (ringC_.size() <= 3) return false;
ring(b, ringC_);
if (ringC_.size() <= 3) return false;
return qNew > 2.0f * qOld + 0.02f && glm::dot(m1, m2) > 0.5f * k1 * k2;
}
if (glm::dot(n1, n2) <= 0.94f * l1 * l2) return false; // a crease: flipping would change the shape
if (glm::dot(m1, m2) <= 0.9f * k1 * k2) return false;
std::vector<uint32_t>& r = ringC_;
auto valence = [&](uint32_t v, int& target) {
ring(v, r);
target = boundaryVertex(v) ? 4 : 6;
return int(r.size());
};
int ta, tb, tc, td;
const int va = valence(a, ta), vb = valence(b, tb), vc = valence(c, tc), vd = valence(d, td);
if (va <= 3 || vb <= 3) return false;
auto sq = [](int x) { return x * x; };
const int before = sq(va - ta) + sq(vb - tb) + sq(vc - tc) + sq(vd - td);
const int after = sq(va - 1 - ta) + sq(vb - 1 - tb) + sq(vc + 1 - tc) + sq(vd + 1 - td);
if (after >= before) return false;
return qNew >= 0.5f * qOld;
}
void DynamicTopology::flip(uint32_t a, uint32_t b, uint32_t c, uint32_t d) {
uint32_t tris[4];
if (edgeTriangles(a, b, tris) != 2) return;
const Mesh& m = *mesh_;
uint32_t t1 = tris[0], t2 = tris[1];
// t1 holds a -> b.
{
const glm::uvec3& tri = m.triangles[t1];
int k = 0;
while (k < 3 && tri[k] != a) ++k;
if (tri[(k + 1) % 3] != b) std::swap(t1, t2);
}
setTriangle(t1, glm::uvec3(c, a, d));
setTriangle(t2, glm::uvec3(d, b, c));
++stats.flips;
++ops_;
}
void DynamicTopology::flipPass() {
// The interior edges of the triangles around changed vertices inside the brush, in a fixed order.
std::vector<std::pair<uint32_t, uint32_t>> candidates;
for (uint32_t v : changedV_) {
if (deadV_[v]) continue;
for (uint32_t t : mesh_->vertexTriangles(v)) {
const glm::uvec3& tri = mesh_->triangles[t];
for (int c = 0; c < 3; ++c) {
const uint32_t a = tri[c], b = tri[(c + 1) % 3];
if (a < b && candidate(a, b)) candidates.emplace_back(a, b);
}
}
}
// And the longest edge of every sliver under the brush and its mirror images (a brush can squash triangles
// flat too).
for (uint32_t t : slivers_) {
if (t >= mesh_->triangleCount() || deadT_[t]) continue;
const glm::uvec3& tri = mesh_->triangles[t];
const auto& p = mesh_->positions;
if (quality(p[tri.x], p[tri.y], p[tri.z]) >= 0.05f) continue;
int longest = 0;
for (int c = 1; c < 3; ++c)
if (len2(tri[c], tri[(c + 1) % 3]) > len2(tri[longest], tri[(longest + 1) % 3])) longest = c;
const uint32_t a = tri[longest], b = tri[(longest + 1) % 3];
candidates.emplace_back(std::min(a, b), std::max(a, b));
}
std::sort(candidates.begin(), candidates.end());
candidates.erase(std::unique(candidates.begin(), candidates.end()), candidates.end());
std::vector<std::pair<uint32_t, uint32_t>> edges;
struct Plan {
uint32_t a, b, c, d;
};
std::vector<Plan> plans;
for (const auto& [a0, b0] : candidates) {
if (ops_ >= maxOps_) break;
if (deadV_[a0] || deadV_[b0] || locked(a0) || locked(b0)) continue;
uint32_t c, d;
if (!flipGain(a0, b0, c, d)) continue;
orbit(a0, b0, edges);
if (edges.size() > 1 && orbitSharesTriangle(edges)) continue;
plans.clear();
bool ok = true;
for (const auto& [x, y] : edges) {
Plan pl{x, y, 0, 0};
if (locked(x) || locked(y) || !flipGain(x, y, pl.c, pl.d)) {
ok = false;
break;
}
plans.push_back(pl);
}
if (!ok) continue;
if (orbitIncomplete_ && !mirrorMaps_.empty()) ++stats.unpaired;
for (const Plan& pl : plans) flip(pl.a, pl.b, pl.c, pl.d);
}
}
// Moves each changed vertex inside the brush halfway to the centre of its neighbours, along the surface
// (free vertices only), which evens out the triangles the splits and collapses made.
void DynamicTopology::relaxPass() {
Mesh& m = *mesh_;
std::vector<std::pair<uint32_t, glm::vec3>> moves;
std::vector<uint32_t>& r = ringC_;
uint32_t other[2];
const float r2 = radius_ * radius_;
for (uint32_t v : changedV_) {
if (deadV_[v] || locked(v)) continue;
bool in = glm::dot(m.positions[v] - center_, m.positions[v] - center_) <= r2;
for (const SymCopy& s : mirrorSigns_) {
const glm::vec3 d0 = m.positions[v] - s.point(center_);
in = in || glm::dot(d0, d0) <= r2;
}
if (!in) continue;
if (featureEdges(v, other) != 0) continue;
ring(v, r);
if (r.size() < 3) continue;
glm::vec3 avg(0.0f);
for (uint32_t u : r) avg += m.positions[u];
avg /= float(r.size());
const glm::vec3 n = faceNormalAt(v);
glm::vec3 d = avg - m.positions[v];
d -= n * glm::dot(d, n);
moves.emplace_back(v, d * 0.5f);
}
// Applied one by one, each only if no triangle around it turns over or goes flat.
const float minArea = 1e-4f * target_ * target_;
for (const auto& [v, d] : moves) {
const glm::vec3 to = m.positions[v] + d;
bool ok = true;
for (uint32_t t : m.vertexTriangles(v)) {
const glm::uvec3& tri = m.triangles[t];
glm::vec3 o[3], q[3];
for (int c = 0; c < 3; ++c) {
o[c] = m.positions[tri[c]];
q[c] = tri[c] == v ? to : o[c];
}
const glm::vec3 nOld = glm::cross(o[1] - o[0], o[2] - o[0]), nNew = glm::cross(q[1] - q[0], q[2] - q[0]);
const float lNew = glm::length(nNew);
if (lNew < minArea || glm::dot(nOld, nNew) <= 0.5f * glm::length(nOld) * lNew) {
ok = false;
break;
}
}
if (!ok) continue;
recordVertex(v);
m.positions[v] = to;
if (!m.base.empty()) m.base[v] += d;
}
}
void DynamicTopology::gatherRegion() {
queryRegion();
if (mirrorSigns_.empty()) return;
// Every vertex of the triangles under each mirror image of the brush, to pair up.
std::vector<uint32_t>& verts = regionVerts_;
std::vector<uint32_t> tris;
verts.clear();
if (seen_.size() < mesh_->vertexCount()) seen_.resize(mesh_->vertexCount() + mesh_->vertexCount() / 4, 0);
auto addCorners = [&](const std::vector<uint32_t>& ts) {
for (uint32_t t : ts)
for (int c = 0; c < 3; ++c) {
const uint32_t v = mesh_->triangles[t][c];
if (seen_[v] == mirrorStamp_) continue;
seen_[v] = mirrorStamp_;
verts.push_back(v);
}
};
// With a margin around each image of the brush: the mirror images of the corners found under one must be
// among those found under the others, though the sides never match exactly.
const float reach = radius_ * 1.25f + target_ * 2.0f;
bvh_->queryTriangles(*mesh_, center_, reach, tris);
addCorners(tris);
for (const SymCopy& s : mirrorSigns_) {
bvh_->queryTriangles(*mesh_, s.point(center_), reach, tris);
addCorners(tris);
}
// Matched within a third of the edge length (the target, or the mesh's own where it is finer, so the
// search grid's cells hold a vertex or two however fine the mesh is).
std::vector<float> lengths;
const size_t stride = std::max<size_t>(1, regionTris_.size() / 1024);
for (size_t i = 0; i < regionTris_.size(); i += stride) {
const glm::uvec3& tri = mesh_->triangles[regionTris_[i]];
lengths.push_back(glm::distance(mesh_->positions[tri.x], mesh_->positions[tri.y]));
}
float typical = target_;
if (!lengths.empty()) {
std::nth_element(lengths.begin(), lengths.begin() + std::ptrdiff_t(lengths.size() / 2), lengths.end());
typical = std::min(typical, lengths[lengths.size() / 2]);
}
eps_ = std::max(typical * 0.3f, 1e-7f);
matchMirrors(verts);
}
bool DynamicTopology::remesh(Mesh& mesh, BVH& bvh, const glm::vec3& center, float radius, float edgeLength,
std::span<const SymCopy> mirrors) {
const auto clock = std::chrono::steady_clock::now();
moved_.clear();
recordedNow_.clear();
if (!dyntopoBlocker(mesh).empty() || !(edgeLength > 0.0f) || !(radius > 0.0f)) return false;
if (mesh_ && mesh_ != &mesh) return false; // (another mesh mid-stroke)
if (!mesh_) {
// A former subdivision level (its levels deleted) may still derive its adjacency from them: store it.
if (mesh.implicitAdjacency()) mesh.rebuildTopology();
if (!mesh.beginDynamicAdjacency()) return false;
mesh_ = &mesh;
bvh_ = &bvh;
startVertices_ = uint32_t(mesh.vertexCount());
startTriangles_ = uint32_t(mesh.triangleCount());
undo_ = std::make_unique<TopologyUndo>();
vertRec_.assign((mesh.vertexCount() + 63) / 64, 0);
triRec_.assign((mesh.triangleCount() + 63) / 64, 0);
deadV_.assign(mesh.vertexCount(), 0);
deadT_.assign(mesh.triangleCount(), 0);
changedVFlag_.assign(mesh.vertexCount(), 0);
if (!mesh.uvs.empty()) { // a remeshed surface has no UVs: they come back with undo
undo_->uvs = std::move(mesh.uvs);
mesh.uvs.clear();
mesh.topologyDirty = true;
}
}
center_ = center;
radius_ = radius;
target_ = edgeLength;
splitLen2_ = (edgeLength * 4.0f / 3.0f) * (edgeLength * 4.0f / 3.0f);
collapseLen2_ = (edgeLength * 0.6f) * (edgeLength * 0.6f);
mirrorSigns_.assign(mirrors.size() > 1 ? mirrors.begin() + 1 : mirrors.end(), mirrors.end());
// Each copy's inverse (a mirror is its own; a radial turn's is the opposite turn), without the identity.
mirrorInverse_.clear();
if (!mirrorSigns_.empty()) {
const std::vector<size_t> inv = symmetryInverses(mirrors);
for (size_t k = 1; k < inv.size(); ++k) mirrorInverse_.push_back(inv[k] > 0 ? inv[k] - 1 : k - 1);
}
mirrorMaps_.resize(mirrorSigns_.size());
if (++mirrorStamp_ == 0) { // (wrapped: forget every old entry)
for (MirrorMap& map : mirrorMaps_) std::fill(map.stamp.begin(), map.stamp.end(), 0);
mirrorStamp_ = 1;
}
ops_ = 0;
maxOps_ = 6000; // (bounds a dab's time: a big brush over fine triangles coarsens them over several dabs)
gatherRegion();
if (regionTris_.empty()) return false;
splitPass();
bvh.refitChanged(mesh);
queryRegion();
collapsePass();
flipPass();
relaxPass();
const bool changed = !changedV_.empty() || !changedT_.empty();
compact();
// Rings and normals of everything that changed, the BVH's boxes, and what the renderer must patch.
const uint32_t nv = uint32_t(mesh.vertexCount());
for (uint32_t v : changedV_)
if (v < changedVFlag_.size()) changedVFlag_[v] = 0;
std::vector<std::pair<uint32_t, uint32_t>> moves(moved_.begin(), moved_.end());
std::sort(moves.begin(), moves.end());
std::vector<uint32_t> verts;
verts.reserve(changedV_.size());
for (uint32_t v : changedV_) {
if (v < nv) {
verts.push_back(v);
continue;
}
// (Past the end now: moved down, or removed.)
const auto it = std::lower_bound(moves.begin(), moves.end(), std::make_pair(v, 0u));
if (it != moves.end() && it->first == v) verts.push_back(it->second);
}
std::sort(verts.begin(), verts.end());
verts.erase(std::unique(verts.begin(), verts.end()), verts.end());
changedV_.clear();
changedVFlag_.resize(nv, 0);
for (uint32_t v : verts) {
ring(v, scratch2_);
mesh.setNeighbors(v, scratch2_);
mesh.markDirty(v);
for (uint32_t t : mesh.vertexTriangles(v)) bvh.touchTriangle(t); // (moved vertices: relaxed, collapsed)
}
mesh.updateNormals(verts);
bvh.refitChanged(mesh);
mesh.changedTriangles.insert(mesh.changedTriangles.end(), changedT_.begin(), changedT_.end());
changedT_.clear();
lastMs = std::chrono::duration<double, std::milli>(std::chrono::steady_clock::now() - clock).count();
return changed;
}
std::unique_ptr<TopologyUndo> DynamicTopology::finish(Mesh& mesh, BVH& bvh) {
if (!mesh_) return nullptr;
mesh.endDynamicAdjacency();
if (bvh.degraded()) bvh.build(mesh);
std::unique_ptr<TopologyUndo> undo = std::move(undo_);
undo->vertexCount = startVertices_;
undo->triangleCount = startTriangles_;
mesh_ = nullptr;
bvh_ = nullptr;
std::vector<uint64_t>().swap(vertRec_);
std::vector<uint64_t>().swap(triRec_);
std::vector<uint8_t>().swap(deadV_);
std::vector<uint8_t>().swap(deadT_);
std::vector<uint8_t>().swap(changedVFlag_);
// (The mirror maps and the vertex stamps stay for the next stroke: their stamps make them empty, and
// sized for the whole mesh they would cost a pass over it to make again.)
std::vector<uint64_t>().swap(gridKeys_);
std::vector<uint32_t>().swap(gridHead_);
std::vector<uint32_t>().swap(gridNext_);
std::vector<uint32_t>().swap(regionVerts_);
if (undo->vertexSlots.empty() && undo->triangleSlots.empty() && undo->uvs.empty()) return nullptr;
return undo;
}
} // namespace sf